Masala #0601

Xotira 240 MB Vaqt 1000 ms Qiyinchiligi 90 %
2.9 (Baholar 23)
14
Muallif: Shahzod

  

Massivlar soni.

Sizga n , n ta son a1,a2,a3...ana_1,a_2,a_3...a_n va p tub son beriladi. Sizning vazifangiz y(y1,y2,y3...yn)y ( y_1 , y_2 , y_3...y_n) to'plamlar sonini topingki ular quyidagi shartlarni bajarsin

1. (1in)0yiai.(1 \le i \le n) 0 \le y_i \le a_i.

2.  (y1+y2++yny1,y2,y3,,yn)mod p=0\begin{pmatrix} y_1 + y_2 + \dots + y_n \\ y_1, y_2, y_3, \dots, y_n \end{pmatrix} mod \ p = 0 (bu yerda mod qoldiq degani). Agar bu narsaga tushunmagan bo'lsangiz bu linkni bosing.

Bu son juda katta bo'lishi shuning uchun uni 109+710^9+7 ga bo'lgandagi qoldiqqa tenglang.


Kiruvchi ma'lumotlar:

Birinchi qatorda n(1n11)n(1 \le n \le 11) va p(1p106)p(1 \le p \le 10^6) beriladi.

Keyingi qatorda n ta son a1,a2,a3...ana_1,a_2,a_3...a_n (1ai109)(1 \le a_i\le10^9).


Chiquvchi ma'lumotlar:

yy to'plamlar sonini 109+710^9+7 ga bo'lgandagi qoldiqni chiqaring.


Misollar
# input.txt output.txt
1
4 3
1 3 2 4
76
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin