Pudding and Coins

Pudding is playing a game that has $n$ levels. There are a total of $n(n+1)/2$ coins spread out among the levels. Specifically, $i$th level has $p_i$ coins where $p_1, p_2, \cdots, p_n$ form a permutation of $1, 2, \cdots, n$. Pudding wants to pick all the coins in each level. However, her game character can only carry $B$ coins in a level where $B$ is the capacity of her bag. In level $1$, $B=1$ and after completing each level, she stores the collected coins in a bank. Thus, the bag is emptied after each level and the capacity $B$ increases by $1$. So if $n=4$ and the $p_i$ are $2, 1, 4, 3$, she will be able to take $1+1+3+3=8$ coins from the game.

Pudding knows that the game has $n$ levels. However, she doesn't know the permutation $p_1, p_2, \cdots, p_n$. She has many queries in mind. A query of $q_i$ asks how many permutations $p_1,\cdots, p_n$ are there such that she will pick exactly $q_i$ coins after finishing the whole game. Note that in each level, she picks as many coins as she possibly can.

Help her answer these queries. But since the counts are huge, you have to output it modulo $1000000000$.

Input

The first line of input will contain a positive integer $n$ ($1 \leq n \leq 100$). The next line will contain a positive integer $t$ ($1 \leq t \leq 100$), the number of queries. Each of the next $t$ lines will contain a positive integer $q_i$ ($1 \leq q_i \leq 10000$), the number of coins she will pick.

Output

Output $t$ lines. The $i$-th line will contain the answer to $i$-th query.

Sample

Input	Output
3 3 6 4 10	1 3 0