D. Валера ба тэнэгүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн сайхан өдөр $n$ тэнэгүүд жагсан бие биенээ $1$-ээс $n$ тоогоор дугаарлав. Тэнэг бүр өөр дугаартай ба тэд энэ тэнэглэл дуусахаас өмнө өөрсдийн дугаараа солихгүйгээр шийдэв.

Тэнэг бүрт $k$ сумтай гар буу бий. Үүнээс гадна $i$ дугаартай тэнэгт харгалзах магадлал $p_i$ буюу түүний буудсан өөр нэг тэнэгийгээ буудаж алах магадлал юм.

Тэнэгүүд хэдэн үе тэнэгтэхээр шийдсэн бөгөөд. Үе бүрт: Яг одоо амьд буй тэнэг бүр хамгийн бага дугаартай амьд байгаа тэнэгийг буудна (Тэнэгүүд тэнэг хэдийч өөрийгөө буудахаар тийм тэнэг биш тийм болохоор хамгийн бага дугаартай тэнэг дараах тэнэгээ буудна). Үе бүрт бүх буудалт яг нэг зэрэг гүйцэтгэгдэнэ. Хэрвээ яг ганц тэнэг үлдвэл ямар ч буудалт болохгүй.

За тэхээр одоо нөхцөл байдал гэх зүйлийг тайлбарлъя. Нөхцөл байдал нь ямар нэг үед амьд байгаа тэнэгүүдийн дугаарын олонлог юм. Боломжтой нөхцөл гэдэг нь ямар нэгэн $j$ ($0 ≤ j ≤ k$) үеийн дараа тухайн нөхцөл байдал үүсч болж байх юм.

Валера $p_1, p_2, ... , p_n$ болон $k$-г мэдэж байгаа. Валерад ялгаатай боломжтой нөхцөл байдлын тоо олж өгч тусална уу?

Оролт

Эхний мөрөнд хоёр бүхэл тоо тэнэгүүдийн тоо $n$, болон тэнэг бүрт өгөх сумны тоо $k$ ($1 ≤ n, k ≤ 3000$) өгөгдөнө.

Хоёрдохь мөрөнд $n$ ширхэг бүхэл тоон цуваа болох тэнэг бүрийн байгаа онох магадлал $p_1, p_2, ... , p_n$ ($0 ≤ p_i ≤ 100$) магадлал хувиар өгөгдөнө.

Гаралт

Хариу болох ганц тоог хэвлэ.

Орчуулсан: byambadorjp

Жишээ тэстүүд

Оролт
3 3
50 50 50
Гаралт
7
Оролт
1 1
100
Гаралт
1
Оролт
2 1
100 100
Гаралт
2
Оролт
3 3
0 0 0
Гаралт
1

Тэмдэглэл

In the first sample, any situation is possible, except for situation ${1, 2}$.

In the second sample there is exactly one fool, so he does not make shots.

In the third sample the possible situations are ${1, 2}$ (after zero rounds) and the "empty" situation ${}$ (after one round).

In the fourth sample, the only possible situation is ${1, 2, 3}$.

Сэтгэгдлүүдийг ачааллаж байна...