Bims
k-dimensional Pascal's simplex is a k-dimensional figure where cell with coordinates (i_1, i_2, ..., i_k) contains value, where i_j ≥ 0 and n = i_1 + i_2 + ... + i_k.
Example:
1-dimensional Pascal's simplex is in nite line of ones.
2-dimensional Pascal's simplex is the usual Pascal's triangle.
3-dimensional Pascal's simplex is an in nite tetrahedron, which consists of all combinations of a kind and so on.
Suppose, we have k-dimensional Pascal's simplex, in which all combinations are computed modulo p (p is prime number). Consider n-th layer of this simplex (the one where all combinations of n are written). Find the number of non-zero elements of this layer. Since that number can be large, it's necessary to write it modulo 10^9+7.
Input
Three numbers k (1 ≤ k ≤ 10^3), p (2 ≤ p ≤ 10^6 + 3, p is prime number) and t (1 ≤ t ≤ 10^5) are given in the first line. Each of next t lines has one number n_i (0 ≤ n_i ≤ 10^18), that is number of the layer.
Output
Exactly t lines, each containing amount of non-zero elements on n_i-th simplex's layer, modulo 10^9 + 7 for correspoding n_i.