All submissions for this problem are available.
Santa and Banta are buddies. Santa has a good sense of humour, but Banta is unable to or partially understands some jokes.
Now Santa has with him N jokes he wishes to tell to Banta. Due to lack of time, he cannot tell all of them and has to choose R jokes for Banta. The total value of all the jokes he tells Banta is Fibonacci ( N C R ).
Note that, Fibonacci(1)=Fibonacci(2)=1 and
Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2) for n > 2.
However, Banta is unable to comprehend all the jokes. The value of jokes he understands is the total value of all jokes Santa tells Banta modulus some value M.
Given N, R and M, your job is to compute the value of jokes Banta understands.
First line contains T ,number of test cases to follow.
Next T lines follows, each line containing 3 space separated integers, N, R and M.
The output contains T lines, each having the value of jokes Banta understands.
- 0 ≤ N,R ≤ 105
- 1 ≤ M ≤ 107
- Sum of N over all test cases ≤ 105
2 2 100
2 1 100
3 1 100
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions