Зоосны Хослол II

2s

512MB

1141

0%

Dynamic Programming

$n$ зоосоос бүрдсэн мөнгөний систем өгөгдөнө. Зоос бүр эерэг бүхэл утгатай. Боломжит зоосуудыг ашиглан $x$ дүнг үүсгэх ялгаатай эрэмбэлэгдсэн аргуудын тоог тоол.

Жишээ нь зоосууд $\{2,3,5\}$ , дүнг $9$ бол $3$ арга бий:

$2+2+5$
$3+3+3$
$2+2+2+3$

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ , $x$ байна: зоосын тоо, хүссэн мөнгөний дүн.

Хоёр дахь мөрөнд зоос бүрийн утгууд $c_1,c_2,\dots,c_n$ хоорондоо ялгаатай $n$ бүхэл тоо байна.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: аргуудын тоог $10^9+7$ -д хуваасан үлдэгдэл.

Хязгаарлалт

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

Жишээ

Оролт1

3 9
2 3 5

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...