俾你一個正整數 $N$ 同一個質數 $P$。
對於 $1, 2, \cdots, N$ 嘅一個排列 $(a_1, a_2, \cdots, a_N)$,定義佢嘅分數 $f(a)$ 如下。
$$f(a) = \max\{ia_i \mid i = 1, 2, \cdots, 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
說明
對於第一個範例,例如 $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$。