\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{1} ≤ \textbf{k} ≤ \textbf{10^3}), \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{10^6 + 3}, \textbf{p} простое) и \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10^5}). В каждой из следующих \textbf{t} строк находится одно число \textbf{n_i} (\textbf{0 }≤ \textbf{n_i} ≤ \textbf{10^18}) - номер слоя. \OutputFile Вывести \textbf{t }строк, в каждой из которых для соответствующего \textbf{n_i} вывести количество ненулевых элементов на \textbf{n_i}-том слое симплекса, по модулю \textbf{10^9 + 7}.