Fibonacci numbers (2)

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 P61833.

Problem information

Author: Salvador Roura

Generation: 2026-03-10T19:46:25.995Z

© Jutge.org, 2006–2026.
https://jutge.org