\includegraphics{https://static.e-olymp.com/content/83/83e3ccdca562abd66cf7639389aaf801f67b5637.jpg} \textbf{k}-dimensional Pascal's simplex is a \textbf{k}-dimensional figure where cell with coordinates (\textbf{i_1}, \textbf{i_2}, ..., \textbf{i_k}) contains value, where \textbf{i_j} ≥ \textbf{0} and \textbf{n} = \textbf{i_1} + \textbf{i_2} + ... + \textbf{i_k}. Example: \textbf{1}-dimensional Pascal's simplex is in nite line of ones. \textbf{2}-dimensional Pascal's simplex is the usual Pascal's triangle. \includegraphics{https://static.e-olymp.com/content/1d/1d9898e695cdb4beae6d59b3bd8b01cd8e59d20e.jpg} \textbf{3}-dimensional Pascal's simplex is an in nite tetrahedron, which consists of all combinations of a kind and so on. Suppose, we have \textbf{k}-dimensional Pascal's simplex, in which all combinations are computed modulo \textbf{p} (\textbf{p} is prime number). Consider \textbf{n}-th layer of this simplex (the one where all combinations of \textbf{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 \textbf{10^9+7}. \InputFile Three numbers \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^3}), \textbf{p }(\textbf{2} ≤ \textbf{p} ≤ \textbf{10^6 + 3}, \textbf{p} is prime number) and \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10^5}) are given in the first line. Each of next \textbf{t }lines has one number \textbf{n_i} (\textbf{0 }≤ \textbf{n_i} ≤ \textbf{10^18}), that is number of the layer. \OutputFile Exactly \textbf{t }lines, each containing amount of non-zero elements on \textbf{n_i}-th simplex's layer, modulo \textbf{10^9 + 7} for correspoding \textbf{n_i}.