406065: GYM102253 J Journey with Knapsack

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.

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 < a_2 < \ldots < 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$$$.

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.

1 1
1
1
2 2
1 2
3 4
3 3
1 2 3
2 3 3

Case #1: 1
Case #2: 2
Case #3: 6