You are given the following recurrences,

F[0] = F[1] = G[0] = 0

G[1] = 1

Input

First line contains the following 6 numbers in order : a, b, c, d, e, and f.

Next line contains Q, the number of queries. The following Q lines contain a single integer each: n

Output

For each query parameter n, output the sum H[0] + H[1] +......+ H[n] modulo 1,000,000,007 in a separate line.

Constraints

1 <= Q <= 100,000

All other input parameters lie in the range [0, 1,000,000,000]