# 3009. Coins (II)

In a strange shop there are $n$ types of coins of value $A_1, A_2, \ldots, A_n$. $C_1, C_2, \ldots, C_n$ denote the number of coins of value $A_1, A_2, \ldots, A_n$ respectively. You have to find the number of ways you can make $K$ using the coins.

For example, suppose there are three coins $1, 2, 5$ and we can use coin $1$ at most $3$ times, coin $2$ at most $2$ times and coin $5$ at most $1$ time. Then if $K = 5$ the possible ways are:

• 1112
• 122
• 5

So, 5 can be made in 3 ways.

### 输入格式

Input starts with an integer $T$ ($T \le 10$), denoting the number of test cases.

Each case starts with a line containing two integers $n$ ($1 \le n \le 100$) and $K$ ($1 \le K \le 10~000$). The next line contains $2n$ integers, denoting $A_1, A_2, \ldots, A_n, C_1, C_2, \ldots, C_n$ ($1 \le A_i \le 100~000, 1 \le C_i \le 1~000$). All $A_i$ will be distinct.

### 输出格式

For each case, print the case number and the number of ways K can be made. Result can be large, so, print the result modulo $100~000~007$.

### 样例

Input
2
3 5
1 2 5 3 2 1
4 20
1 2 3 4 8 4 2 1

Output
Case 1: 3
Case 2: 9


43 人解决，44 人已尝试。

64 份提交通过，共有 110 份提交。

2.8 EMB 奖励。