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

fib(0) = 0 ⇒ 0 mod 5 = 0

fib(1) = 1 ⇒ 1 mod 5 = 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.