БинКоэф
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, p і t. У кожному з наступних t рядків знаходиться одне число n_i —номер шару.
Вихідні дані
Рівно t рядків, у кожному з яких для відповідного n_i вивести кількість ненульових елементів на n_i-тому шарі симплекса, по модулю 10^9+7.
Обмеження
1 ≤ k ≤ 10^3
2 ≤ p ≤ 10^6+3, p — просте.
1 ≤ t ≤ 10^5
0 ≤ n_i ≤ 10^18