ŠIOM — Kodinimas

Laiko ribojimas: 3s

Atminties ribojimas: 256MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Kodinimas

Yra projektas, kuriam reikia parašyti lygiai $m$ eilučių kodo. Yra $n$ programuotojų, kurie dirba prie to projekto, $i$ -tasis iš jų padaro lygiai $a_i$ klaidų kiekvienoje kodo eilutėje.

Pavadinkime seką $v_1,v_2,\\dots,v_n$ ( $0\\leqv_i$ ) $planu$ , jei $v_1+v_2+\\dots+v_n=m$ . Programuotojai laikosi plano tokiu būdu: iš pradžių pirmas programuotojas parašo $v_1$ eilutę kodo, tada antras programuotojas parašo dar $v_2$ eilučių kodo, ir t.t. Pavadinkime planą $geru$ , jei iš viso yra padaryta ne daugiau kaip $b$ klaidų iš viso.

Jūsų užduotis yra suskaičiuoti, kiek yra gerų planų. Kadangi tas skaičius gali būti labai didelis, pateikite to skaičiaus liekaną dalinant iš $mod$ .

Pradiniai duomenys

Pirmoje eilutėje duoti skaičiai $n,m,b,mod$ ( $1\\leqn,m\\leq500$ , $0\\leqb\\leq500$ , $1\\leqmod\\leq10^9+7$ ) — programuotojų kiekis, kodo eilučių kiekis, didžiausiais galimas klaidų kiekis ir skaičius, naudojamas išvesti atsakymui.

Antroje eilutėje yra duoti $n$ skaičių $a_1,a_2,\\dots,a_n$ ( $0\\leqa_i\\leq500$ ) — kiekvieno programuotojo paliekamų klaidų kiekvienoje eilutėje kiekis.

Rezultatai

Tegu $k$ yra gerų planų skaičius. Jums reikia išvesti liekaną $k$ dalinant iš $mod$ .

Pavyzdys

Duomenys	Rezultatai
3 3 6 10 1 1 3	7

Šeštadieninė informatikos olimpiadininkų mokykla

Kodinimas

Pradiniai duomenys

Rezultatai

Pavyzdys