Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Pudding and Coins

By upobir · Limits 1s, 512 MB

Pudding is playing a game that has nn levels. There are a total of n(n+1)/2n(n+1)/2 coins spread out among the levels. Specifically, iith level has pip_i coins where p1,p2,,pnp_1, p_2, \cdots, p_n form a permutation of 1,2,,n1, 2, \cdots, n. Pudding wants to pick all the coins in each level. However, her game character can only carry BB coins in a level where BB is the capacity of her bag. In level 11, B=1B=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 BB increases by 11. So if n=4n=4 and the pip_i are 2,1,4,32, 1, 4, 3, she will be able to take 1+1+3+3=81+1+3+3=8 coins from the game.

Pudding knows that the game has nn levels. However, she doesn't know the permutation p1,p2,,pnp_1, p_2, \cdots, p_n. She has many queries in mind. A query of qiq_i asks how many permutations p1,,pnp_1,\cdots, p_n are there such that she will pick exactly qiq_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 10000000001000000000.

Input

The first line of input will contain a positive integer nn. The next line will contain a positive integer tt, the number of queries. Each of the next tt lines will contain a positive integer qiq_i, the number of coins she will pick.

1n1001 \leq n \leq 100

1t1001 \leq t \leq 100

1qi100001 \leq q_i \leq 10000

Output

Output tt lines. The iith line will contain the answer to iith query.

Sample

InputOutput
3
3
6
4
10
1
3
0

Discussion

Statistics


60% Solution Ratio

NirjhorEarliest, 1M ago

serotoninFastest, 0.0s

adnan_tokyLightest, 8.4 MB

serotoninShortest, 659B

Submit

Login to submit

Editorial

Note we need to count permutations such that min⁡(1,p1)+min⁡(2,p2)+⋯+min⁡(n,pn)=s\min(1, p_1)+\min(2...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.