Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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,

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:

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

提交代码