RECPWSUM - 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

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.


hide comments
suhash: 2022-12-15 01:56:44

@Francky: Sorry for the really late response (been off SPOJ for a while). Thanks for correcting the description! :)

It is correct that 'a' and 'b' don't feature into the time complexity (they might be important for the solution depending on the method used though). Re: O(T×k²×log(n)), the expected solution has lower complexity (you need to get rid of a 'k' factor here).

Francky: 2022-07-11 17:57:50

There's only T=4 and not 5 in sample test case. I can edit the description :wink: ; it is now correct.

---

I have a O(T×k²×log(n)) solution, regardless a and b, but it can only solve one case every 6s using Python... Are the conditions on a, b relevant for this task ?

Thanks


Added by:suhash
Date:2020-06-01
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own (Inspired by FIBPWSUM)