BinKoeff#4594
-ölçülü Paskal simpleksi — bu, ölçülü bir fiqurdur, burada (i_1, i_2, ..., i_k) koordinatlı hüceyrədə bir qiymət yerləşir, burada i_j \geq 0 və n = i_1 + i_2 + \dots + i_k.
Məsələn:
1-ölçülü Paskal simpleksi sonsuz sayda birdən ibarət bir sıradır.
2-ölçülü Paskal simpleksi adi Paskal üçbucağıdır.
3-ölçülü Paskal simpleksi sonsuz bir tetraedrdir və bütün belə kombinasiyalardan ibarətdir və s.
Tutaq ki, bizdə ədədinə görə qalıqla ( sadə ədəddir) bütün kombinasiyalar hesablanmış -ölçülü bir Paskal simpleksi var. Bu simpleksin -ci qatını nəzərə alaq (yəni, verilmiş üçün bütün kombinasiyalar). Bu qatdakı sıfırdan fərqli elementlərin sayını tapın. Bu ədəd böyük ola bilər, ona görə cavabı 10^9 + 7-yə görə qalıqla çap edin.
Birinci sətirdə üç ədəd verilir: (1 \leq k \leq 10^3), (2 \leq p \leq 10^6+3, burada sadədir) və (1 \leq t \leq 10^5).
Sonrakı sətrin hər birində bir tam ədəd n_i (0 \leq n_i \leq 10^{18}) — qat nömrəsi verilir.
Dəqiq olaraq sətir çıxış verin. Hər bir uyğun n_i üçün -ölçülü Paskal simpleksinin n_i-ci qatında sıfırdan fərqli elementlərin sayını 10^9 + 7 modulunda çap edin.
Nümunə 1
1 \leq k \leq 10^3
2 \leq p \leq 10^6+3, sadədir
1 \leq t \leq 10^5
0 \leq n_i \leq 10^{18}