Fibonacci numbers (2) P74219


Statement
 

pdf   zip

thehtml

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

Input

The input consists of several pairs of n and m. Assume 0 ≤ n ≤ 109 and 2 ≤ m ≤ 103.

Output

For every given pair, print Fn 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++