Masala #0247
Qaytim
Bitboy do’konga borib o’ziga kerakli narsalarni olganidan so’ng savdogarga xarid qilgan narsalari uchun pul to’ladi, Nurmuhammad to’lagan pul xarid qilgan mahsuloti narxidan \(M\) so’m ko’p edi, va shu \(M\) so’mni savdogan qaytim qilib Nurmuhammadga berishi kerak. Savdogarda jami \(N\) xil turdagi pullardan yetarlicha miqdorda bor. Ya’ni, \(C_1\) so’mlik pul, \(C_2\) so’mlik pul, va hokazo, \(C_N\) so’mlik pullardan yetarlicha miqdorda bor. Savdogar Nurmuhammadga aynan \(M\) so’mni necha xil usulda qaytim qilishi mumkinligini aniqlang!
Kirish faylining dastlabki satrida ikkita butun son, \(N\) va \(M (1 \le N*M \le 10^6)\) sonlari kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(C(1 \le C_i \le 10^6)\) pul miqdorlarining turlari kiritiladi.
Chiqish fayliga yagona butun son, so’ralgan javobni \(1000000007(10^9+7)\) ga bo’lgandagi qoldiqni chop eting!
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 1 2 3 |
5 |
1-testga izoh:
- {1,1,1,1,1}
- {1,1,1,2}
- {1,1,3}
- {1,2,2}
- {2,3}
Telegram kanalimizga obuna bo'ling