Fişierul intrare/ieşire:	power.in, power.out	Sursă	AGM 2019, runda nationala
Autor	Costin Oncescu	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	3.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/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 p_i. Războinicul este destul de priceput şi observă că există anumiţi parametri intregi ne-negativi a₁, ..., a_k care satisfac următoarea ecuaţie:

p_i = a₁ * 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₁, ..., p_k). Misiunea lui iniţială a fost să găsească puterea totala în zilele d₁, ..., d_Q, modulo 10⁹ + 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 ≤ a_i ≤ 10⁹
• 1 ≤ p₁, ..., p_k ≤ 10⁹
• 1 ≤ Q ≤ 1.000
• 1 ≤ d₁, ..., d_Q ≤ 10¹⁸

Exemplu

Cum se trimit solutii?