XIV LO im. S. Staszica

Treść
Dany jest ciąg a_i liczb naturalnych. Wyrazy tego ciągu można policzyć z następującego ogólnego wzoru:

a1=b1

a2=b2

…

ak=bk

ai=c1 ai - 1 + c2 ai - 2 + … + ck ai - k (dla i>k)

gdzie b_j i c_j (1<=j<=k) są podanymi liczbami naturalnymi. Twoim zadaniem jest dla podanych b_j, c_j oraz n, obliczyć wartość a_n. Ponieważ a_n może być bardzo dużą liczbą, jako wynik należy podać a_n modulo 10⁹ (miliard).


Wejście
Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=50) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych
Jeden zestaw danych obejmuje cztery wiersze. W pierwszym wierszu znajduje się liczba całkowita k (1<=k<=50). W drugim wierszu znajduje się k liczb całkowitych, oddzielonych pojedynczymi spacjami, odpowiednio b₁,b₂,…,b_k (0<=b_j<=10⁹). W trzecim wierszu podanych jest k liczb całkowitych, oddzielonych pojedynczymi spacjami, odpowiednio c₁,c₂,…,c_k (0<=c_j<=10⁹). W ostatnim, czwartym wierszu, znajduje się liczba całkowita n (1<=n<=10⁹).

Wyjście
Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest obliczona wartość a_n modulo 10⁹.


Przykład

dane wejściowe:
3
3
6 6 3
5 8 9
2
3
8 8 2
3 7 5
5
3
0 2 2
3 9 4
4

wynik:
6
360
24

[Zgłoś rozwiązanie]   [Moje zgłoszenia]