Masala #0247

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 25 %
3.9 (Baholar 7)
14

  

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 MM so’m ko’p edi, va shu MM so’mni savdogan qaytim qilib Nurmuhammadga berishi kerak. Savdogarda jami NN xil turdagi pullardan yetarlicha miqdorda bor. Ya’ni, C1C_1 so’mlik pul, C2C_2 so’mlik pul, va hokazo, CNC_N so’mlik pullardan yetarlicha miqdorda bor. Savdogar Nurmuhammadga aynan MM so’mni necha xil usulda qaytim qilishi mumkinligini aniqlang!


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, NN va M(1NM106)M (1 \le N*M \le 10^6) sonlari kiritiladi. Ikkinchi satrda NN ta butun son, C(1Ci106)C(1 \le C_i \le 10^6) pul miqdorlarining turlari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish fayliga yagona butun son, so’ralgan javobni 1000000007(109+7)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}
  2. {1,1,1,2}
  3. {1,1,3}
  4. {1,2,2}
  5. {2,3}
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin