Fişierul intrare/ieşire:power.in, power.outSursăAGM 2019, runda nationala
AutorCostin OncescuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test3.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Power

Un războinic cu părul de argint a fost însărcinat cu o slujbă neobişnuită. El este trimis la o anumită breasla de razboinici şi isi noteaza puterea totală a tuturor membrilor breslei în fiecare zi. În ziua i, puterea este un număr întreg ne-negativ pi. Războinicul este destul de priceput şi observă că există anumiţi parametri intregi ne-negativi a1, ..., ak care satisfac următoarea ecuaţie:

pi = a1 * pi-1 + ... + ak * pi-k

Din nefericire, indiferent cat de bun este razboinicul, dupa ce a adormit, el isi da seama ca a uitat tot ce si-a notat, cu exceptia lui k, a sirului a si a primelor valori k din sirul p (adica p1, ..., pk). Misiunea lui iniţială a fost să găsească puterea totala în zilele d1, ..., dQ, modulo 109 + 7. Puteţi să-l ajutaţi să faca asta?

Date de intrare

Fişierul de intrare power.in va contine pe primul rand pe T, numarul de teste din fisier.
Fiecare test va contine 4 randuri. Primul rand contine numerele intregi k si Q.
Al doilea rand va contine k valori intregi, valorile sirului a.
Al treilea rand va contine k valori intregi, primele k valori ale sirului p.
Al patrulea rand va contine Q valori intregi, valorile sirului d.

Date de ieşire

În fişierul de ieşire power.out afisati raspunsurile pentru fiecare test, in ordine.
Pentru fiecare test, afisati valorile intregi cerute, in ordine.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ k ≤ 20
  • 1 ≤ ai ≤ 109
  • 1 ≤ p1, ..., pk ≤ 109
  • 1 ≤ Q ≤ 1.000
  • 1 ≤ d1, ..., dQ ≤ 1018

Exemplu

power.inpower.out
1
3 4
1 2 3
3 2 1
2 5 15151 232322323
2
22
706889415
66083255
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?