給定一個正整數 $N$ 和一個質數 $P$。 對於 $1, 2, \dots, N$ 的一個排列 $(a_1, a_2, \dots, a_N)$，定義其分數 $f(a)$ 如下：

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

請找出所有排列的分數總和除以 $P$ 的餘數。

輸入格式

第一行包含 $N$ 和 $P$，兩者以空格分隔。($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ 為質數)

輸出格式

輸出所有排列的分數總和除以 $P$ 的餘數。

範例

輸入格式 1

10 100000007

輸出格式 1

77379290

輸入格式 2

1000 998244353

輸出格式 2

168695631

Note

對於第一個範例，例如 $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$。

所有 $10!$ 個排列的分數總和為 $277379304$，該總和除以質數 $P = 10^8 + 7$ 的餘數為 $77379290$，因此輸出 $77379290$。請注意，對於此輸入，質數 $P$ 為 $9$ 位整數 $10^8 + 7$。