FIBTWIST - Fibonacci With a Twist

no tags 

Fibonacci numbers are given by 

  • f(n) = f(n-1) + f(n-2)

with f(0) = 0 and f(1) = 1.

first number of series — 0  1  1  2  3  5  8  13 

Now let's have a new series called "Fibonacci Twist" which is given by 

  • ft(n) = ft(n-1) + ft(n-2) + (n-1)

with ft(0) = 0 and ft(1) = 1.

with first few number in the series — 0  1  2  5  10  19  34  59 

Now your task is to find ft(n).

Since the number can be big you have to find the result mod M.

Input

first line having single number 't' — number of test cases.

Next t lines have 2 number each 'n' and 'M'

Output

Single number given the n-th term mod M

Example

Input:
3
5 20
10 77
15 111

Output:
19
45
69

Constraints

  • 10 ≤ t ≤ 100
  • 0 ≤ n ≤ 109
  • 100 ≤ M ≤ 109

Explanation

  1. ft(5) is 19. 19 % 20 = 19
  2. ft(10) is 276. 276 % 77 = 45
  3. ft(15) is 3177. 3177 % 111 = 69

hide comments
Pankaj Gudlani: 2013-02-01 09:16:13

more test cases please...
it is giving WA... :(

符号器: 2013-01-22 09:49:11

@pranshul..agreed with u...

$!:D: 2012-12-19 05:37:41

O(n) giving tle :(
is dere any other way to do it ?

Last edit: 2012-12-19 05:38:11
triveni: 2012-12-18 10:12:27

for those , getting wrong answer: use mod(%) function cleverly . This may give wrong answer. I got one WA for that..
finally AC :)

007: Name stolen: 2012-07-21 11:45:54

please check my solution its giving NZEC
http://www.spoj.pl/files/src/7352268/

Gurpreet Singh: 2012-06-30 19:45:45

Please check my submissions. Don't know why its getting WA. I have checked it using data type as 'int' and 'long long'. Yet WA...

Suraj D: 2012-05-31 03:44:00

@Problem Setter. Could you please tell me where I fail? Submission Id 7065432. Thanks.

Adrian Jaskó³ka: 2012-05-28 07:46:26

TO PROBLEMSETTER:
Test cases are weak. Look at my submission 7050497. I have there table int c[3][3] (instead of long long!).
1
1000000000 1000000007
output should be 21, and my code is giving 347003493.

Last edit: 2012-05-28 07:47:01

Added by:Devil D
Date:2012-04-19
Time limit:0.100s-1s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own