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 <= 10^9
  • 100 <= M <= 10^9

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
smso: 2023-06-06 17:40:54

If you solve by using formula, beware of overflow when n is big and M is small, e.g.
1
1000000000 37
9

adist98: 2019-06-19 00:09:23

Can anyone please explain this negative modulus case? I can't seem to wrap my head around this and somehow i see this everywhere.

milw0rm_007: 2018-06-19 10:25:17

@Devil D What is the problem with my solution?(Sub. ID 21860369)

sandeep_4141: 2017-06-23 11:51:02

same as FIBOSUM !!

divya_28: 2017-01-29 15:25:46

Do FIBOSUM before this.

MishThi: 2015-09-14 19:56:12

Solved FIBOSUM and then did some extra paperwork.. And Bazinga!
**Do take care of negative modulus if programming in C.

Mayank Garg: 2015-08-19 16:35:50

No need of matrix exponentiation , if u r ready to do some calculations ..!! A simple formula ;) AC in 0.0s :p

Saksham : 2015-08-10 23:26:15

take care of -ve modulus

anshal dwivedi: 2015-08-10 14:17:37

Ac in one go! by using 4X4 matrix...

:.Mohib.:: 2015-06-24 11:15:18

2nd century on spoj with great que....learned a lot.... :)


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