GENFIB - Generalized Fibonacci

no tags 

In this problem, we generalize the Fibonacci sequence.

    G[n] = a * G[n - 1] + b * G[n - 2] + c

where a, b and c are constants given in input. Also:

  • G[1] = 1
  • G[2] = 1

You need to evaluate the nth number module m in the generalized Fibonacci sequence where m is given in input.

Input

The first line contains number of test cases t. Each of the next t subsequent lines contain a, b, c, n and m.

t <= 1000

0 <= a, b, c <= 1e9

1 <= m <= 1e9

1 <= n <= 1e18

Output

Print answer for each test case on a separate line.

Example

Input:
1
1 1 0 3 5

Output:
2

hide comments
Programming Club, IITK: 2017-01-18 12:03:15

Sorry but this problem is set as an assignment problem for the data structure course at IIT Kanpur. We will move it into the tutorial after the grading is done.

=(Francky)=> In tutorial section, the grading is possible in the same way. Please move it ASAP.

Last edit: 2017-01-18 13:39:06
Francky: 2017-01-18 10:33:15

This problem should be moved to tutorial for several reasons : we yet have tons of easy recurrence problems ; issue with initial test files ; 'young' psetter with 0 problem solved should start with tutorial problems for sure.

Programming Club, IITK: 2017-01-18 10:24:58

Sorry for the inconvenience caused. There was a small bug in the test files. We are trying to rejudge all solutions but it is recommended that you submit again.

Vipul Srivastava: 2017-01-18 05:15:31

I think now this question should be removed. It is definitely incomplete.

akash333: 2017-01-17 07:53:02

Something wrong in the test cases it seems

Last edit: 2017-01-17 07:55:09
Shivam Garg: 2017-01-15 23:32:21

There is something wrong for sure. Can you please check? And moreover, please specify the use of m (if it to be used in modulo operation ) ?

abdou_93: 2017-01-15 23:24:53

i think there is something wrong in (input or output) file!

Last edit: 2017-01-15 23:26:01

Added by:Programming Club, IITK
Date:2017-01-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU