#RECPWSUM. Recurrence Power Sum

    ID: 3911 远端评测题 10000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>combinatoricsgenerating-functionmatrixexpobinets-formula

Recurrence Power Sum

You are given a series defined by the following recurrence:

f0 = x, f1 = y

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

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

f0k + f1k + f2+ ... + fnk

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, bx, 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  109

0 ≤ n ≤ 1015

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

</p>

Explanation

In all the sample test cases, f0 = 0, f1 = 1, fn = fn-1 + fn-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 00 + 10 + 10 + 20 = 4.
  • For the second case, the required sum is 01 + 11 + 11 + 21 = 4.
  • For the third case, the required sum is 02 + 12 + 12 + 22 + 32 = 15.
  • For the fourth case, the required sum is 03 + 13 + 13 + 23 + 33 = 37.

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