Trong cuộc thi ICPC cấp khoa vào Chủ Nhật tuần trước, đội của Kichirou đang bước vào những giây phút cuối cùng đầy căng thẳng. Họ đang đứng ở vị trí thứ hai, và nếu muốn giành chiến thắng, họ bắt buộc phải giải thêm một bài toán nữa.

Còn chưa đầy 30 phút trên đồng hồ. Nếu không thể tìm ra lời giải kịp thời, cơ hội vươn lên dẫn đầu sẽ vụt mất.

Kichirou chăm chú nhìn vào đề bài vừa xuất hiện trên màn hình. Đây là một bài toán về dãy số đặc biệt, bắt đầu với hai giá trị cố định: ~F_1 = 3, \quad F_2 = 7.~

Tuy nhiên, từ số thứ ba trở đi, dãy số này tuân theo một quy luật bí ẩn:

~F_n = (F_{n-1} \times F_{n-2} + 1) \mod M, \quad \text{với } n \geq 3.~

Hãy giúp Kichirou tìm ra một thuật toán tối ưu để giải quyết bài toán này trước khi hết thời gian!

Input

• Dòng duy nhất chứa 2 số nguyên dương ~n~, ~M~. ~(1 \leq n \leq 10^6, 1 \leq M \leq 10^{12})~.

Output

• Dòng duy nhất in kết quả của ~F_n~.

Scoring

• Subtask 1 ~(20\%)~: ~n \leq 25, M \leq 10^3~.
• Subtask 2 ~(40\%)~: ~n \leq 10^6, M \leq 10^6~.
• Subtask 3 ~(40\%)~: ~n \leq 10^6, M \leq 10^{12}~.

Samples

Sample Input

25 24

Sample Output

15