БинКоэф
k-мерный симплекс Паскаля - это такая k-мерная фигура, что в ячейке (i_1, i_2, ..., i_k) записано число , где i_j ≥ 0, а n = i_1 + i_2 + ... + i_k.
Пример:
1-мерный симплекс Паскаля — это бесконечная строка из единиц
2-мерный симплекс Паскаля — это обычный треугольник Паскаля
3-мерный симплекс Паскаля - это бесконечный тетраэдр, в котором записаны сочетания вида и так далее.
Допустим, что у нас есть k-мерный симплекс Паскаля, в котором все сочетания записаны по модулю p (p простое). Рассмотрим n-тый слой этого симплекса (тот, где записаны все сочетания из n). Необходимо найти количество ненулевых элементов на этом слое. Так как это число может оказаться большим, необходимо вывести его по модулю 10^9 + 7.
Входные данные
В первой строке даны три числа k (1 ≤ k ≤ 10^3), p (2 ≤ p ≤ 10^6 + 3, p простое) и t (1 ≤ t ≤ 10^5). В каждой из следующих t строк находится одно число n_i (0 ≤ n_i ≤ 10^18) - номер слоя.
Выходные данные
Вывести t строк, в каждой из которых для соответствующего n_i вывести количество ненулевых элементов на n_i-том слое симплекса, по модулю 10^9 + 7.