Fibonacci numbers (2) P74219

For every given pair of natural numbers $n$ and $m$, compute $F_n \bmod 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 \le n \le 10^9$ and $2 \le m \le 10^3$.

Output

For every given pair, print $F_n \bmod m$.

Hint

Consider the problem problem://problemsjutge.org:problems/algorismia/divide-and-conquer/eleva-matriu.pbm.