БінКоеф#4594
-вимірний симплекс Паскаля — це -вимірна фігура, в якій комірка з координатами (i_1, i_2, \ldots, i_k) містить певне значення, де i_j \geq 0 та n = i_1 + i_2 + \dots + i_k.
Наприклад:
-вимірний симплекс Паскаля — це нескінченний ряд одиниць.
-вимірний симплекс Паскаля — стандартний трикутник Паскаля.
-вимірний симплекс Паскаля — нескінченний тетраедр, який складається з усіх таких комбінацій, і так далі.
Нехай у вас є -вимірний симплекс Паскаля, де всі комбінації обчислюються за модулем (де — просте число). Розглянемо -ий рівень цього симплексу (тобто всі комбінації для заданого ). Знайдіть кількість ненульових елементів на цьому рівні. Оскільки ця кількість може бути великою, виведіть її за модулем 10^9 + 7.
У першому рядку задано три числа: (1 \leq k \leq 10^3), (2 \leq p \leq 10^6+3, де — просте), та (1 \leq t \leq 10^5).
Кожен з наступних рядків містить одне ціле число n_i (0 \leq n_i \leq 10^{18}) — номер рівня.
Виведіть рівно рядків. Для кожного n_i виведіть кількість ненульових елементів на n_i-му рівні -вимірного симплексу Паскаля за модулем 10^9 + 7.
Приклад 1
1 \leq k \leq 10^3
2 \leq p \leq 10^6+3, — просте
1 \leq t \leq 10^5
0 \leq n_i \leq 10^{18}