ŠIOM — Retrospektyvinė seka

Laiko ribojimas: 4s

Atminties ribojimas: 128MB

Duomenų failas: rseka.in

Rezultatų failas: rseka.out

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

Retrospektyvinė seka

Retrospektyvinė seka yra tokia rekursyvi seka, kurios pirmieji $N$ narių yra apibrėžti, o kiekvienas tolesnis narys yra ankstesnių narių suma, t. y. $F_m=F_{m-k_1}+F_{m-k_2}+\\cdots+F_{m-k_{C-1}}+F_{m-k_{C}}$ , $1\\leqk_i\\leqN$ , $k_i<k_{i+1}$ , $1\\leqk_i\\leqN$ .

Pavyzdžiui, Fibonači seka yra tokia retrospektyvinė seka, kur $N=2$ , $F_1=1$ , $F_2=1$ , $C=2$ , $k_1=1$ , $k_2=2$ .

Raskite duotos retrospektyvinės sekos $M$ -ąjį narį moduliu MOD = 1000000009.

Pradiniai duomenys

Pirmoje eilutėje – testų skaičius T. ( $1\\leqT\\leq100$ )

Kiekvieno testo pirmoje eilutėje yra 3 sveikieji skaičiai: N, M ir C. ( $1\\leqN\\leq20$ , $1\\leqM\\leq10^{18}$ , $1\\leqC\\leqN$ )

Kiekvieno testo antroje eilutėje yra N sveikųjų skaičių – pirmieji sekos nariai. ( $0\\leqF_i\\leq10$ )

Kiekvieno testo trečioje eilutėje yra yra C sveikųjų skačių – $k_1$ , $k_2$ , ..., $k_C$ .

Rezultatai

Kiekvienam testui išveskite vieną eilutę su skaičiumi $F_M$ moduliu MOD.

Pavyzdys

Duomenys	Rezultatai
3 2 2 2 1 1 1 2 2 7 2 1 1 1 2 3 100000000000 3 0 1 2 1 2 3	1 13 48407255

Šeštadieninė informatikos olimpiadininkų mokykla

Retrospektyvinė seka

Pradiniai duomenys

Rezultatai

Pavyzdys