For every given pair of natural numbers n and m,
compute F_{n} modm,
where F_{n} is the n-th Fibonacci number (starting at 0).

Input

The input consists of several pairs of n and m.
Assume 0 ≤ n ≤ 10^{9}
and 2 ≤ m ≤ 10^{3}.

Output

For every given pair, print F_{n} modm.

Hint

Consider the problem .

Public test cases

**Input**

0 100 10 100 10 9 1000 876

**Output**

0 55 1 411

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++