题目描述

$\texttt{Dr.Orange}$ is conducting research in animal psychology, and one of the studies involves inferring the number of each animal in the ecosystem based on their dietary habits. It is known that there are $n$ types of animals in the ecosystem, and the $i$-th type of animal consumes $a_i$ portions of bait per time. $\texttt{Dr.Orange}$'s experiment was conducted over $m$ days, and on the $i$-th day, $t_i$ portions of bait were deployed, with all bait being consumed each day. For each of the $m$ days, different animals take turns to consume bait. You need to answer how many different eating sequences. Two sequences are the same only if the animals at each position in the sequence are of the same species. Since this result can be very large, please provide the answer modulo $10^9+7$.

输入格式

The first line contains two integers $n, m(1\le n,m\le 100)$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i(1\le a_i\le 100)$.

The third line contains $m$ integers, representing the amount of bait deployed on the $i$-th day, $t_i(1\le t_i\le 10^9)$.

输出格式

Output one line with $m$ integers, where the $i$-th integer represents the answer for the $i$-th day modulo $10^9+7$.

5 3
5 4 4 2 3
5 8 3

3
16
1

10 5
9 1 6 5 10 4 9 2 7 6
64 92 43 30 2

566507809
840913760
608266829
85862862
2

提示

For the first day of the first sample, there are three possible eating sequences: $[1]$, $[4,5]$, and $[5,4]$. The numbers in the sequences represent the types of animals.