You are given a recursion in the following form -
f(n) = c₁f(n-1) + c₂f(n-2) + ... + c_kf(n-k)

And the base cases f(0), f(1), ..., f(k-1)

Given a number n. Find f(n). As the number can be very big. Output f(n) mod 10⁹+9

Input

First line contains the recursion. f(n) = c₁f(n-1) + c₂f(n-2) + ... + c_kf(n-k).  (c_i <= 10000, k <= 9)

If any c_i = 1, it will not be shown.

The next line contains the base cases f(0), f(1), ... , F(k-1)

Next line will contain a number t (t<= 100000) the number testcases.

Next t lines will contain a number n (n<= 2³²-1)

Output

Print f(n) mod 10⁹ + 9

Example

Input:
f(n) = 2f(n-1) + f(n-2) 
0 1
1
5
Output:
29