Fibonacci Modulo Calculation

The Fibonacci sequence is defined as follows:

• \(f_1 = 1\)
• \(f_2 = 1\)
• \(f_n = f_{n-1} + f_{n-2}\) for \(n \ge 3\) (and \(n\) is an integer)

Your task is to compute \(f_n \bmod p\), that is, the remainder when \(f_n\) is divided by \(p\).

Note: Use efficient algorithms to handle large values of \(n\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(p\) separated by a space.

\(n\) represents the index in the Fibonacci sequence, and \(p\) the modulus.

outputFormat

Output a single integer: \(f_n \bmod p\).

sample

5 3

2