A Problem With Fibonacci Sequence

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  Fibonacci sequence is well-known in the world. We define Fibonacci sequence as follows: F(0) = 0, F(1) = 1. F(n) = F(n-1) + F(n-2), n>=2. It’s easy for us to calculate F(n) mod m. But this time we want to make the problem more difficult. We want to calculate the formula:
is the combination number. 

Input

  First line is the testcase T. Following T lines, each line is two integers n, m ( 0 ≤ n ≤ 109, 1 ≤ m ≤ 30000 )

Output

  Output the answer mod m

Sample Input

2
1 30000
2 30000

Sample Output

1
3

Hint

 

Source

2009湖南大学校赛