Consider a sequence \(f_n\)\((n \ge 0)\). You do not know the values of \(f_n\). However, function \(F(x)\) defined as follows:
\(F(x) = \sum \limits_{n \ge 0} f_nx^n = \frac{1 + dx + ex^2}{1+ax+bx^2+cx^3}\)

You are given \(a, b, c, d, e, N\). Your task is to calculate \(f_N\).

Since this value can be very large, print it modulo \(1000000007(10^9+7)\). You can read about modular arithmetic here.

You are given \(T\) test cases.

Input format

The first line contains a single integer \(T\) that denotes the number of test cases.
For each test case:
- Six space-separated integers denoting the values of \(a, b, c, d, e, N\).

Output format

For each test case (in a separate line), print the value \(f_N\) modulo \((10^9+7)\).

Constraints

\( 1 \le T \le 10^4 \\ -10^9 \le a, b, c, d, e \le 10^9 \\ 0 \le N \le 10^{18}\)