描述

There 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$?

It 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.

Input

The first line contains an integer $T(1 \le T \le 20)$, which is the number of test cases.

For each test case:

The 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.

For 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$.

For the next $Q$ lines, each line contains a single integer: $S(1 \le S \le 10000)$, representing the queried weight.

Output

For 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$.

• intput

• output

思路

• 完全背包二进制优化，因为数量都是$2^n-1$,也就是说二进制的所有位数都是1，就可以保证不会有相同种类相同数量的。
• $dp[i]=(dp[i]+dp[i-cost]) \% mod$;

代码

-------------本文结束 感谢您的阅读-------------