FIBTWIST - Fibonacci With a Twist

no tags

Fibonacci numbers are given by

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

with f(0) = 0 & 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 & ft(1) = 1.

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

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

 < Previous 1 2 3 4 5 6 Next > 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.... :) r0bo_dart: 2015-06-22 19:59:22 Ac at 1 go... solve FIBOSUM before this to get an idea about the realm of Fibonacci :P