Journey with Knapsack

KazaQ has a knapsack with volume $2 \cdot n$ and $n$ kinds of food, where the $i$-th food's volume is $i$ and the number of it is $a_i$ $(1 \leq i \leq n)$ meaning that the number of the $i$-th food that KazaQ would like to store into the knapsack is no more than $a_i$, otherwise he would feel sick. KazaQ has a unique taste, therefore all the $a_i$ are distinct.

KazaQ plans to make a journey but after that he needs to store some food and one piece of equipment into the knapsack. He has $m$ pieces of equipment, of which the $i$-th piece's volume is $b_i$ $(1 \leq i \leq n)$. Notice that volumes of different pieces may be the same.

Assuming that two plans are distinct if and only if they contain different pieces of equipment or there exists at least one integer $k$ $(1 \leq k \leq n)$ satisfying the number of the $k$-th food to store into the knapsack in this two plans are different, KazaQ is intend to know what is the total number of distinct plans for storing one piece of equipment and some food into the knapsack fully. Can you help him?

The answer may be very large, so you only need to give the value of the answer modulo $10^9 + 7$.

The input contains multiple test cases.

For each test case:

The first line contains two positive integers $n$ and $m$, satisfying $1 \leq n \leq 5 \cdot 10^4, 1 \leq m \leq 2 \cdot n$.

The second line contains $n$ distinct non-negative integers $a_1, a_2, \cdots, a_n$, satisfying $0 \leq a_1 < a_2 < \cdots < a_n \leq 2 \cdot n$.

The third line contains $m$ positive integers $b_1, b_2, \cdots, b_m$, satisfying $1 \leq b_1, b_2, \cdots, b_m \leq 2 \cdot n$.

About $100$ test cases in total, where no more than $5$ cases satisfy $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 of 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

2017 Multi-University Training Contest - Team 1