Bạn được cho một số nguyên dương $N$ và một số nguyên tố $P$. Với một hoán vị $(a_1, a_2, \dots, a_N)$ của $1, 2, \dots, N$, định nghĩa điểm số $f(a)$ của nó như sau:

$$f(a) = \max\{i \cdot a_i \mid i = 1, 2, \dots, N\}$$

Hãy tìm số dư khi tổng các điểm số của tất cả các hoán vị được chia cho $P$.

Dữ liệu vào

Dòng đầu tiên chứa $N, P$ theo thứ tự, cách nhau bởi dấu cách. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ là số nguyên tố)

Dữ liệu ra

In ra số dư khi tổng các điểm số của tất cả các hoán vị được chia cho $P$.

Ví dụ

Dữ liệu vào 1

10 100000007

Dữ liệu ra 1

77379290

Ghi chú

Đối với ví dụ đầu tiên, chẳng hạn, $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$. Tổng các điểm số của tất cả $10!$ hoán vị là $277379304$, và số dư khi chia tổng này cho số nguyên tố $P = 10^8 + 7$ là $77379290$, vì vậy in ra $77379290$. Lưu ý rằng đối với dữ liệu vào này, số nguyên tố $P$ là số nguyên có 9 chữ số $10^8 + 7$.

Dữ liệu vào 2

1000 998244353

Dữ liệu ra 2

168695631