Trong đợt họp fan tập thể, Anh Domixi đã nghĩ ra một bài tập thể dục mới cho các anh em Do tộc!

Giống như trước, ~N~ anh em (~1 \le N \le 10^4~) đang đứng thành một hàng. Bạn thứ ~i~ từ trái sang tương ứng với chỉ số ~i~ với mỗi ~1 \le i \le N~. Anh Domixi bảo mọi người lặp lại bước sau cho đến khi các bạn trở về đúng thứ tự ban đầu.

Cho một hoán vị ~A~ có độ dài ~N~, các anh em sẽ đổi vị trí sao cho bạn thứ ~i~ từ trái sang trước khi đổi sẽ trở thành bạn thứ ~A_i~ từ trái sang sau khi đổi.

Ví dụ, nếu ~A = (1, 2, 3, 4, 5)~ thì các bạn chỉ thực hiện một bước. Nếu ~A = (2, 3, 1, 5, 4)~, thì các bạn thực hiện sáu bước. Thứ tự các bạn từ trái sang phải sau mỗi bước như sau:

• 0 bước: ~(1, 2, 3, 4, 5)~
• 1 bước: ~(3, 1, 2, 5, 4)~
• 2 bước: ~(2, 3, 1, 4, 5)~
• 3 bước: ~(1, 2, 3, 5, 4)~
• 4 bước: ~(3, 1, 2, 4, 5)~
• 5 bước: ~(2, 3, 1, 5, 4)~
• 6 bước: ~(1, 2, 3, 4, 5)~

Hãy tìm tổng của tất cả các số nguyên dương ~K~ sao cho tồn tại một hoán vị có độ dài ~N~ yêu cầu các bạn thực hiện đúng ~K~ bước.

Vì kết quả có thể rất lớn, hãy in ra đáp án theo modulo ~M~ (~10^8 \le M \le 10^9 + 7~, ~M~ là số nguyên tố).

Input

Dòng duy nhất chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^4~, ~10^8 \le M \le 10^9 + 7~, ~M~ là số nguyên tố) – độ dài hoán vị và số modulo.

Output

In ra một số nguyên duy nhất là tổng của tất cả các giá trị ~K~ hợp lệ theo modulo ~M~.

Example

Input

5 1000000007

Output

21              

Note

Ở test ví dụ với ~N = 5~, các giá trị ~K~ có thể đạt được là ~{1, 2, 3, 4, 5, 6}~, tương ứng với các cách phân hoạch ~5~ thành các chu trình có bội chung nhỏ nhất khác nhau. Tổng là ~1 + 2 + 3 + 4 + 5 + 6 = 21~.