You are given a series defined by the following recurrence:

f₀ = x, f₁ = y

f_n = a * f_n-1 + b * f_n-2

You are required to find the summation of the following series:

f₀^k + f₁^k + f₂^k + ... + f_n^k

The values a, b, x, y, n, k will be provided. Since the answer can be large, output it modulo 1000000007.

Input

The first line contains a single integer T denoting the number of test cases. Each test case consists of six space separated integers on a single line, in the order: a, b, x, y, n, k.

Output

For each test case, output a single integer (on a separate line) denoting the summation of the series as mentioned above.

Constraints

1 ≤ T ≤ 500

0 ≤ a, b ≤ 100

0 ≤ x, y ≤ 10⁹

0 ≤ n ≤ 10¹⁵

0 ≤ k ≤ 1000 

Example

Input:
4
1 1 0 1 3 0
1 1 0 1 3 1
1 1 0 1 4 2
1 1 0 1 4 3
Output:
4
4
15
37

Explanation

In all the sample test cases, f₀ = 0, f₁ = 1, f_n = f_n-1 + f_n-2, which is the regular Fibonacci series. The first few terms of the sequence are 0, 1, 1, 2, 3, 5, ....

• For the first case, the required sum is 0⁰ + 1⁰ + 1⁰ + 2⁰ = 4.
• For the second case, the required sum is 0¹ + 1¹ + 1¹ + 2¹ = 4.
• For the third case, the required sum is 0² + 1² + 1² + 2² + 3² = 15.
• For the fourth case, the required sum is 0³ + 1³ + 1³ + 2³ + 3³ = 37.

Note: Time limit is set leniently to allow slow languages to pass.