Just a bit sorted

Jurgen Guntherswarchzhaffenstrassen is known for his guitar playing and for the harsh way he teaches his students. Most people miss one more thing about him. He also likes numbers.

Jurgen has been studying sorted lists lately, and he got bored. Sorted lists are too predictable and there are too few of them, so he changed the rule a little.

Take a list $\ell$ of $N$ positive integers. The elements do not have to be distinct. Jurgen calls $\ell$ just a bit sorted if for every integer $x > 1$ that occurs in $\ell$, the value $x-1$ occurs at least once before the last occurrence of $x$ in $\ell$. For example:

• $[2, 3, 1, 2]$ is just a bit sorted, because a 1 stands before the last 2 and a 2 stands before the last 3.
• $[2, 3, 4, 3, 2, 1, 3, 4]$ is not just a bit sorted, because every 1 stands after the last 2.
• $[1, 1, 3, 1, 3, 3, 1, 3]$ is not just a bit sorted, because no 2 stands before the last 3. This list has no 2 at all.

Jurgen wants to know how many different just a bit sorted lists of $N$ positive integers not greater than $K$ exist. Two lists are different if they differ in at least one position. Count them for him.

The first line contains the length $N$ of the lists and the number $Q$ of queries ($1 \le N \le 5000$, $1 \le Q \le 1000$). The second line contains the integers $K_1, K_2, \dots, K_Q$. The lists counted in the $i$-th query contain no value greater than $K_i$ ($1 \le K_i \le 10^9$).

Print one line with $Q$ integers separated by single spaces. The $i$-th integer is the number of different just a bit sorted lists of $N$ positive integers not greater than $K_i$. This number can be very large, so print it modulo $10^9+7$.