Bims#4594
A -dimensional Pascal's simplex is a -dimensional figure in which the cell with coordinates (i_1, i_2, \ldots, i_k) contains a value, where i_j \geq 0 and n = i_1 + i_2 + \ldots + i_k.
For example:
The -dimensional Pascal's simplex is an infinite row of ones.
The -dimensional Pascal's simplex is the standard Pascal's triangle.
The -dimensional Pascal's simplex is an infinite tetrahedron, consisting of all such combinations, and so on.
Suppose we have a -dimensional Pascal's simplex, where all combinations are calculated modulo (where is a prime number). Consider the -th layer of this simplex (that is, all combinations for a given ). Find the number of nonzero elements in this layer. Since this number may be large, print it modulo 10^9 + 7.
The first line contains three numbers: (1 \leq k \leq 10^3), (2 \leq p \leq 10^6 + 3, where is a prime), and (1 \leq t \leq 10^5).
Each of the next lines contains a single integer n_i (0 \leq n_i \leq 10^{18}) — the layer number.
Output exactly lines. For each corresponding n_i, print the number of nonzero elements in the n_i-th layer of the -dimensional Pascal's simplex modulo 10^9 + 7.
Esempio 1
1 \leq k \leq 10^3
2 \leq p \leq 10^6 + 3, is prime
1 \leq t \leq 10^5
0 \leq n_i \leq 10^{18}