Cho dãy số ~\left(a_{n}\right)~ được xác định bằng phương pháp truy hồi như sau:

$$ \left\{\begin{array}{l} a_{0}=1, a_{1}=6 \\ a_{n}=6 a_{n-1}-9 a_{n-2} \text { với } n \geq 2 \end{array}\right. $$

Với hai số nguyên dương ~n, m~ cho trước. Hãy tìm số dư khi chia ~a_{n}~ cho ~m~.

Dữ liệu:

• Một dòng duy nhất chứa hai số nguyên dương ~n~ và ~m\left(n, m \leq 10^{18}\right)~ được ghi cách nhau bởi dấu cách.

Kết quả:

• Ghi ra trên một dòng, một số nguyên duy nhất là kết quả theo yêu cầu của bài toán.

Ví dụ:

Sample Input 1

5 100

Sample Output 1

58

Sample Input 2

10 898

Sample Output 2

285