A Problem With Fibonacci Sequence
Time Limit: 1 s
Memory Limit: 64 MB
Submission：10
AC：1
Score：99.94
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 ≤ 10^9, 1 ≤ m ≤ 30000 )
Output
Output the answer mod m.
Samples
input
2
1 30000
2 30000
output
1
3