== include(page="template/taskheader" task_id="power") ==

Poveste şi cerinţă...

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 $p{~i~}$. Războinicul este destul de priceput şi observă că există anumiţi parametri intregi ne-negativi $a{~1~}, ..., a{~k~}$ care satisfac următoarea ecuaţie:
 
$p{~i~} = a{~1~} * p{~i-1~} + ... + a{~k~} * p{~i-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 $p{~1~}, ..., p{~k~}$). Misiunea lui iniţială a fost să găsească puterea totala în zilele $d{~1~}, ..., d{~Q~}$, modulo $10^9^ + 7$. Puteţi să-l ajutaţi să faca asta?

h2. Date de intrare

Fişierul de intrare $power.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $power.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ k ≤ 20$
* $1 ≤ a{~i~} ≤ 10^9^$
* $1 ≤ p{~1~}, ..., p{~k~} ≤ 10^9^$
* $1 ≤ Q ≤ 1.000$
* $1 ≤ d{~1~}, ..., d{~Q~} ≤ 10^18^$

h2. Exemplu
table(example). |_. power.in |_. power.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
3 4
1 2 3
3 2 1
2 5 15151 232322323
| 2
22
706889415
66083255

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="power") ==