Cho dãy số được định nghĩa như sau:

a₁ = 1; a₂ = 2; a_n = a_n-1 + a_n-2

Yêu cầu:

Cho trước một số nguyên dương k (k<=10¹⁶) và m (m <=10⁴). Hãy tính a_k mod m.

Dữ liệu vào: Hai số nguyên dương k và m.

Dữ liệu ra: In ra giá trị a_k mod m.

Input:

4 10000

Output:

5