Задача #0247

Память 16 MB Время 1000 ms Сложность 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!

Входные данные:

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 Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время