HZNUOJ

A Problem With Fibonacci Sequence

Tags:
Time Limit:  1 s      Memory Limit:   64 MB
Submission:4     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

Source

湖南大学2009校赛