Masala #0247

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 25 %

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!

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Chiqish fayliga yagona butun son, so’ralgan javobni \(1000000007(10^9+7)\) ga bo’lgandagi qoldiqni chop eting!

Misollar

#	input.txt	output.txt
1	3 5 1 2 3	5

Izoh:

1-testga izoh:

{1,1,1,1,1}
{1,1,1,2}
{1,1,3}
{1,2,2}
{2,3}

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin