Thầy giáo giao bài tập về nhà cho học sinh của mình với đề bài: mỗi bạn có một tập hợp ~A = (a_1,a_2,a_3,...,a_n)~ là một hoán vị của tập ~{1,2,...,n}~. Với mỗi hoán vị của tập ~{1,2,...,n}~, thầy sẽ giao cho một bạn học sinh; ban đầu, các bạn có hoán vị cơ sở ~P = A^{0}~ ; sau một bước hoán vị ~A^{x}~ sẽ trở thành hoán vị ~A^{x+1}~ theo quy tắc: Số thứ ~i~ trong hoán vị ~A^{x}~ sẽ nằm ở vị trí ~P_i~ sau khi biến đổi.

Nhiệm vụ của mỗi bạn là tìm ra ~x > 0~ với ~x~ là một chu kì biến đổi của ~A~ tối thiểu cần thực hiện để từ hoán vị ~P~ ta trở về được trạng thái ban đầu của nó.

Ví dụ:

• Với ~A=(1,2,3,4,5)~ thì chu kỳ của nó bằng ~1~;

• Với ~A = (2,3,1,5,4)~ chu kỳ là ~6~:
  • Bước ~0: \ A^{0} = (2; 3; 1; 5; 4)~
  • Bước ~1: \ A^{1} = (1; 2; 3; 4; 5)~
  • Bước ~2: \ A^{2} = (3; 1; 2; 5; 4)~
  • Bước ~3: \ A^{3} = (2; 3; 1; 4; 5)~
  • Bước ~4: \ A^{4} = (1; 2; 3; 5; 4)~
  • Bước ~5: \ A^{5} = (3; 1; 2; 4; 5)~
  • Bước ~6: \ A^{6} = (2; 3; 1; 5; 4)~

Đáp án của đề bài là tổng tất cả các kết quả mà học sinh tìm được. Vì số này có thể rất lớn nên thầy chỉ lấy phần dư của nó khi chia cho ~M (10^8 \le m \le 10^9+7, m~ là số nguyên tố).

Dữ liệu

Nhập dữ liệu từ file homework.inp:

• Một dòng chứa hai số nguyên dương ~n,m (n \le 10^4)~.

Kết quả

Ghi ra file homework.out:

• Một số nguyên là đáp án tìm được.

Giới hạn

• ~50\%~ số điểm ứng với giới hạn ~n \le 100~.
• ~50\%~ số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Dữ liệu

3 1000000007

Kết quả

6

Giải thích

• Hoán vị 1 2 3 có chu kì là 1
• Hoán vị 1 3 2 có chu kì là 2
• Hoán vị 2 1 3 có chu kì là 2
• Hoán vị 2 3 1 có chu kì là 3
• Hoán vị 3 1 2 có chu kì là 3
• Hoán vị 3 2 1 có chu kì là 2
• Đáp án: 1 + 2 + 3 = 6