Calculate Fibonacci n-th term modulo m

Fibonacci sequence is defined by obtaining each next term in the sequence by adding up the previous two, while the first two elements are 0 and 1:
Given the number n, you are asked to calculate the n-th Fibonacci numbers modulo m.
As we’re only interested in the result modulo m, the value of n can be very large.

Input

The only line of the input contains two integers n (0 ≤ n ≤ ) and m (1 ≤ m ≤ 50).

Output

The program should print the result of .

Examples

Input
Output
0 5
0
1 5
1
6 5
3

Explanation

  1. fib(0) = 0 ⇒ 0 mod 5 = 0
  1. fib(1) = 1 ⇒ 1 mod 5 = 1
  1. fib(6) = 8 ⇒ 8 mod 5 = 3
 
Hint 1
As we’re calculating the fibonacci numbers modulo m, and the next number always depends on the previous two, the numbers start to repeat at some point. You can try printing many values modulo m and notice the pattern after which they start repeating.
Hint 2
As the numbers start repeating at some point, you can directly calculate the n-th Fibonacci number instead of looping through all of them.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue