{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are $N$ different kinds of transport ships on the port. The $i^{th}$ kind of ship can carry the weight of $V[i]$ and the number of the $i^{th}$ kind of ship is $2^{C[i]} - 1$. How many different schemes there are if you want to use these ships to transport cargo with a total weight of $S$? \u003c/p\u003e\u003cp\u003eIt is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\u003cp\u003eThe first line contains an integer $T(1 \\le T \\le 20)$, which is the number of test cases. \u003c/p\u003e\u003cp\u003eFor each test case: \u003c/p\u003e\u003cp\u003eThe first line contains two integers: $N(1 \\le N \\le 20), Q(1 \\le Q \\le 10000)$, representing the number of kinds of ships and the number of queries.\u003c/p\u003e\u003cp\u003eFor the next $N$ lines, each line contains two integers: $V[i](1 \\le V[i] \\le 20), C[i](1 \\le C[i] \\le 20)$, representing the weight the $i^{th}$ kind of ship can carry, and the number of the $i^{th}$ kind of ship is $2^{C[i]} - 1$.\u003c/p\u003e\u003cp\u003eFor the next $Q$ lines, each line contains a single integer: $S(1 \\le S \\le 10000)$, representing the queried weight.\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\u003cp\u003eFor each query, output one line containing a single integer which represents the number of schemes for arranging ships. Since the answer may be very large, output the answer modulo $1000000007$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 2\n2 1\n1\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}