For every given pair of natural numbers *n* and *m*,
compute *F*_{n} mod*m*,
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} mod*m*.

**Hint**

Consider the problem P61833: “Powers of a matrix”.

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++