Algolymp Educational | Fibofest

Cerință

După foarte multe probleme rezolvate, ai ajuns la Fibofest și ești gata să te relaxezi. Din păcate, pentru a avea acces la toate distracțiile festivalului, trebuie mai întai să îi ajuți pe organizatori cu o listă de $Q$ întrebări. Inițial, organizatorii iți vor da un număr $K$ și două liste, a câte $K$ numere naturale fiecare, denumite $A$ și $W$. Cu acestea, se va defini un șir infinit de numere, $F$, după urmatoarele reguli:

• $F_i$ = $A_i$, pentru $1 \leq i \leq K$;
• $F_i$ = $\sum_{j=1}^K W_j * F_{i - j}$, pentru $i > K$;

Folosind informațiile de mai sus, obiectivul tău este să raspunzi la cele $Q$ întrebări, acestea având urmatoarea formă:
$N$ - Care este valoarea lui $F_N$ modulo $1 \ 000 \ 000 \ 007$?

Date de intrare

Pe prima linie se găsește numărul $K$.
Pe a doua linie se găsesc $K$ valori, reprezentând șirul $A$.
Pe a treia linie se găsesc $K$ valori, reprezentând șirul $W$.
Pe a patra linie se găsește numărul $Q$.
Următoarele $Q$ linii vor conține fiecare câte un număr, $N$, reprezentând întrebarea curentă.

Date de ieșire

Răspunsurile la cele $Q$ întrebari vor fi afișate câte unul pe linie, pentru un total de $Q$ linii în stdout.

Restricții și precizări

• $1 \leq K, Q \leq 200$;
• $0 \leq A_i, W_i \leq 1 \ 000 \ 000 \ 000$;
• $1 \leq N_i \leq 1 \ 000 \ 000 \ 000$;

Exemplu

stdin

2
0 1
1 1
5
6
4
5
3
7

stdout

5
2
3
1
8

Explicație

Șirul $F$ este șirul lui Fibonacci: $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $\dots$.