For every given pair of natural numbers n and m, compute Fn modm, where Fn is the n-th Fibonacci number (starting at 0).
Input
The input consists of several pairs of n and m. Assume 0 ≤ n ≤ 109 and 2 ≤ m ≤ 103.
Output
For every given pair, print Fn modm.
Hint
Consider the problem P61833: “Powers of a matrix”.
Input
0 100 10 100 10 9 1000 876
Output
0 55 1 411