Dãy Fibonacci được định nghĩa:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) với n ≥ 2

Cho n và M, hãy tính F(n) modulo M.

Với n lên đến 10^18, cần sử dụng luỹ thừa ma trận (matrix exponentiation) để tính trong O(log n).

Ma trận truy hồi:

[F(n+1)  F(n)  ]   =   [1  1] ^ n
[F(n)    F(n-1)]       [1  0]

Đầu vào

Một dòng duy nhất gồm hai số nguyên n (0 ≤ n ≤ 10^18) và M (1 ≤ M ≤ 10^9+7).

Đầu ra

Một số nguyên duy nhất là F(n) mod M.

Ví dụ

Input:
10 1000000007

Output:
55

F(10) = 55.