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
sobriquet: 2014-07-01 12:03:03

Learned a lot of new things.If getting WA, use MOD carefully.Very good problem.

Rahul Ranjan: 2014-05-31 18:05:26

getting WA at test case 7....help pls

`Ak: 2014-05-24 10:35:16

I am too getting wa at running 7 any tricky test case ???

Shreyans: 2014-01-02 08:16:37

WA on running...(7)
Is there any tricky cases??

sagar baver: 2013-11-27 16:22:55

for all gettin WA: use mod carefully!!

AlcatraZ: 2013-11-03 21:09:20

It is indeed a "Fibonacci With a Twist".

Pranab Kumar: 2013-09-06 09:52:23

ID:9992546...Pls tell why my answer is wrong showing here. Is that due to this
10<=t<=100
0<=n<=10^9
100<=M<=10^9

or any other reason?

@looser@: 2013-08-07 17:44:24

plz give me more test case
i am getting wrong ans after 4th test case..........

vaibhav gupta: 2013-07-01 15:32:38

Same code is giving TLE and wrong ans..!Don't know what to do..!?

(Tjandra Satria Gunawan)(曾毅昆): 2013-05-09 09:44:05

server is very unstable, exact same code: 0.99s, then 0.97s, and finally 0.21s using recurrence order 2, written in PYTH 2.7


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