Zadanie ASD2

Treść

Masz dany wielomian W. Znasz też punkt x. Znajdź wartość wielomianu W w punkcie x.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba D oznaczająca liczbę zestawów, które za chwile pojawią się na wejściu.
Każdy zestaw składa się najpierw z liczby N oznaczającej rząd wielomianu. Po niej następuje N+1 liczb całkowitych (1<=N<=100.000), które oznaczają kolejne współczynniki wielomianu, rozpoczynając od tego o najwyższej potędze. Na końcu zestawu w drugiej linii znajduje się liczba całkowita x, która oznacza wartość punktu, w którym szukamy wartości wielomianu. (0<=x<=100.000)

Specyfikacja wyjścia

Dla każdego zestawu należy w osobnej linii zapisać jedną liczbę oznaczającą wartość wielomianu w punkcie modulo 10.000

Przykład

Wejście

2
3 2 4 5 0
0
4 9 0 -3 8 1
1

Wyjście

0
15