aprileasy-easy-linear-recurrences

You are given the following recurrences, 

F(n) = a * F(n - 1) + b * G(n - 2) for n ≥ 2

G(n) = c * G(n - 1) + d * F(n - 2) for n ≥2

H(n) = e * F(n) + f * G(n) for n ≥ 0

Input

First line contains the following 10 numbers in order : a, b, c, d, e, f, F[0], F[1], G[0], G[1].

Next line contains a single integer Q, the number of queries. The following Q lines contain a single query 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 ≤ 1,000,000

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

SAMPLE INPUT
1 2 3 4 5 6 1 2 3 4
2
2 
3

SAMPLE OUTPUT
193
609

Source: hackerearth | Difficulty: MEDIUM
Tags: Matrices


Solutions: