FIBTWIST  Fibonacci With a Twist
Fibonacci numbers are given by
 f(n) = f(n1) + f(n2)
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(n1) + ft(n2) + (n1)
with ft(0) = 0 & 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 nth 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
 ft(5) is 19. 19 % 20 = 19
 ft(10) is 276. 276 % 77 = 45
 ft(15) is 3177. 3177 % 111 = 69
hide comments
adist98:
20190619 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:
20180619 10:25:17
@Devil D What is the problem with my solution?(Sub. ID 21860369) 

sandeep_4141:
20170623 11:51:02
same as FIBOSUM !! 

divya_28:
20170129 15:25:46
Do FIBOSUM before this. 

MishThi:
20150914 19:56:12
Solved FIBOSUM and then did some extra paperwork.. And Bazinga!


Mayank Garg:
20150819 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 :
20150810 23:26:15
take care of ve modulus


anshal dwivedi:
20150810 14:17:37
Ac in one go! by using 4X4 matrix... 

:.Mohib.::
20150624 11:15:18
2nd century on spoj with great que....learned a lot.... :) 

r0bo_dart:
20150622 19:59:22
Ac at 1 go... solve FIBOSUM before this to get an idea about the realm of Fibonacci :P 
Added by:  Devil D 
Date:  20120419 
Time limit:  0.100s0.426s 
Source limit:  20000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 