Fibonacci numbers (1) P21926


Statement
 

pdf   zip

html

The Fibonacci numbers Fn are defined as follows:

Fn = ⎧
⎪
⎨
⎪
⎩
0if n = 0 
1if n = 1 
Fn−1 + Fn−2if n ≥ 2

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 Fn modm.

Input

Input consists of several pairs of n and m. Assume 0 ≤ n ≤ 1000 and 2 ≤ m ≤ 108.

Output

For every given pair, print Fn modm.

Public test cases

  • Input

    0 100
10 100
10 9
1000 87654321

    Output

    0
55
1
41825580
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Fortran Python