By Gabriel Dalalio, ITA Brazil
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.
The input consists of several test cases and ends with EOF. Each test case consists of a line with two integers N and M (1 ≤ N ≤ 109, 2 ≤ M ≤ 106).
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 |
1 |