The Fibonacci numbers F_{n} are defined as follows:
F_{n} =  ⎧ ⎪ ⎨ ⎪ ⎩ 

Therefore, the first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
For every given pair of natural numbers n and m, compute F_{n} modm.
Input
Input consists of several pairs of n and m. Assume 0 ≤ n ≤ 1000 and 2 ≤ m ≤ 10^{8}.
Output
For every given pair, print F_{n} modm.
Input
0 100 10 100 10 9 1000 87654321
Output
0 55 1 41825580