FIBPSUM2 - Fibonacci Power Sum (hard)
This problem is a harder version of FIBPWSUM.
The Fibonacci numbers is defined by
and
for .
Given three integers , and , compute the summation
Since the answer can be huge, output it modulo .
Input
The first line contains an integer , denoting the number of test cases. Each test case contains three space separated integers in the order: , and .
Constraints
Output
For each test case, output a single line in the format "Case X: Y" without the quotes. Here, X is the case number and Y is the desired answer denoting the sum of the series.
Example
Input: 5 10 1 1 5 2 2 3 3 4 1000000007 7 9 996969696969696 9 6 Output: Case 1: 143 Case 2: 3540 Case 3: 1340448 Case 4: 880410497 Case 5: 689328397
Credits
Information
There are two test files. The first file is randomly generated while the second file is not.
@Speed Adicts: My solution runs in 1.94s. (approx less than 1s per file)
hide comments
|
Francky:
2020-06-13 23:40:07
@Speed Addicts : remember that challenge section can offer you stuff like : https://www.spoj.com/problems/PWSUMF/
|
|
Scape:
2019-03-16 20:06:42
Haha, I wanted to create a harder version of this problem with the exact same constraints, but looks like you beat me to it :)
|
Added by: | liouzhou_101 |
Date: | 2019-03-04 |
Time limit: | 20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | FIBPWSUM |