\includegraphics{https://static.e-olymp.com/content/83/83e3ccdca562abd66cf7639389aaf801f67b5637.jpg} \textbf{k}-вимірний симплекс Паскаля --- це така \textbf{k}-вимірна фігура, що у комірці (\textbf{i_1}, \textbf{i_2}, ..., \textbf{i_k}) записано число , де \textbf{i_j} ≥ \textbf{0}, а \textbf{n} = \textbf{i_1} + \textbf{i_2} + ... + \textbf{i_k}. Приклад: \textbf{1}-вимірний симплекс Паскаля --- це нескінченний рядок з одиниць \textbf{2}-вимірний симплекс Паскаля --- це звичайний трикутник Паскаля \includegraphics{https://static.e-olymp.com/content/1d/1d9898e695cdb4beae6d59b3bd8b01cd8e59d20e.jpg} \textbf{3}-вимірний симплекс Паскаля --- це нескінченний тетраедр, у якому записано сполучення виду і так далі. Допустимо, що у нас є \textbf{k}-вимірний симплекс Паскаля, у якому усі сполучення записані по модулю \textbf{p} (\textbf{p} --- просте). Розглянеми \textbf{n}-тий шар цього симплексу (той, де записані усі сполучення з \textbf{n}). Необхідно знайти кількість ненульових елементів на цьому шарі. Так як цео число може виявитись великим, необхідно вивести його по модулю \textbf{10^9+7}. \InputFile У першому рядку задано три числа \textbf{k}, \textbf{p} і \textbf{t}. У кожному з наступних \textbf{t} рядків знаходиться одне число \textbf{n_i} ---номер шару. \OutputFile Рівно \textbf{t} рядків, у кожному з яких для відповідного \textbf{n_i} вивести кількість ненульових елементів на \textbf{n_i}-тому шарі симплекса, по модулю \textbf{10^9+7}. \textbf{Обмеження} \textbf{1} ≤ \textbf{k} ≤ \textbf{10^3} \textbf{2} ≤ \textbf{p} ≤ \textbf{10^6+3}, \textbf{p} --- просте. \textbf{1} ≤ \textbf{t} ≤ \textbf{10^5} \textbf{0} ≤ \textbf{n_i} ≤ \textbf{10^18}