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 + f2k + ... + 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, 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 ≤ 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! :)
|
|
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.
|
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) |