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

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) với \(n \ge 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 \le n \le 10^18\)) và M (\(1 \le M \le 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.

Ràng buộc & Subtasks