beecrowd | 1531

Fibonacci Again!

By Gabriel Dalalio, ITA BR Brazil

Timelimit: 3

The famous Fibonacci sequence can be defined as follows:

Your task is simple, calculate the value of the remainder of Fib ( Fib ( N ) ) divided by M.

Input

The input consists of several test cases and ends with EOF. Each test case consists of a line with two integers and M (1 ≤ N ≤ 109, 2 ≤ M ≤ 106).

Output

For each test case, print a line containing an integer equal to the remainder of Fib ( Fib ( N ) ) divided by M.

Sample Input Sample Output

1 100
2 100
3 100
4 100
5 100
5 2
6 100

1
1
1
2
5
1
21