J. Journey with Knapsack
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

KazaQ has a knapsack of volume $$$2 n$$$ and $$$n$$$ kinds of food, where the volume of one piece of the $$$i$$$-th kind of food is $$$i$$$, and the number of pieces of that kind he would like to put into the knapsack is no more than $$$a_i$$$. If he put too much food in it, he would feel uncomfortable. Besides, since he has an odd taste for food, $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ are distinct.

KazaQ plans to go on a journey. Before that, he needs to take some food and one type of equipment he owns. He has $$$m$$$ types of equipment, where the $$$i$$$-th one's volume is $$$b_i$$$, and some types of equipment may have the same volume.

KazaQ intends to know in how many ways he can pack up his belongings into his knapsack to make it full, where two ways are considered different if and only if the types of equipment he carries vary, or in case they are the same, the numbers of at least one kind of food in these two ways are different. Can you help him?

The answer may be extremely large, so you should output the answer modulo $$$(10^9 + 7)$$$ instead.

Input

The input contains multiple (about $$$100$$$) test cases.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 5 \times 10^4$$$, $$$1 \leq m \leq 2 n$$$).

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$0 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 2 n$$$).

The third line contains $$$m$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_m$$$ ($$$1 \leq b_1, b_2, \ldots, b_m \leq 2 n$$$).

It is guaranteed that no more than $$$5$$$ test cases satisfy that $$$n \geq 10^3$$$.

Output

For each test case, output "Case #x: y" in one line (without quotes), where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ denotes the answer to the corresponding case.

Example
Input
1 1
1
1
2 2
1 2
3 4
3 3
1 2 3
2 3 3
Output
Case #1: 1
Case #2: 2
Case #3: 6