A sequential value

★★★★★

6 votes

Arrays, Number Theory, Data Structures, 1-D, Math, Modulus Arithmetic

Details

Problem

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}$

Time Limit: 0.5

Memory Limit: 256

Source Limit:

Explanation

We have $T = 2$ .

In the first test case, $F(x) = \frac{1}{1-x} = 1 + x + x^2 + ..$ , we can see that $f_5$ would correspond to coefficient of $x^5$ which is $1$ .

In the second test case, $F(x) = \frac{1}{1+x} = 1 - x + x^2 - x^3 + ..$ , we can see that $f_1$ would correspond to coefficient of $x$ which is $-1$ . However, the modulo value is $1000000006$ .