Problem Description

As everyone knows, the Fibonacci sequence is a series that satisfies the following properties:

• \( f_1 = 1 \)

• \( f_2 = 1 \)

• \( f_n = f_{n-1} + f_{n-2} \) (\( n \geq 2 \) and \( n \) is an integer)

Please compute the value of \( f_n \mod p \).

Input Format

• Line 1: An integer \( n \).

• Line 2: An integer \( p \).

Output Format

• Line 1: The value of \( f_n \mod p \).

Sample Input and Output

Input Sample #1

5
1000000007

Output Sample #1

5

Input Sample #2

10
1000000007

Output Sample #2

55

Notes

For \( 100\% \) of the data, \( n \leq 10^{30000000}, p < 2^{31} \).

见题面 Input 部分

见题面 Output 部分