Gegeben sind eine positive ganze Zahl $N$ und eine Primzahl $P$.
Für eine Permutation $(a_1, a_2, \cdots, a_N)$ von $1, 2, \cdots, N$ wird ihr Score $f(a)$ wie folgt definiert.
$$f(a) = \max\{ia_i \mid i = 1, 2, \cdots, N\}$$
Bestimme den Rest, wenn die Summe der Scores über alle Permutationen durch $P$ geteilt wird.
Eingabe
Die erste Zeile enthält $N, P$ in dieser Reihenfolge, getrennt durch Leerzeichen. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ ist eine Primzahl)
Ausgabe
Gib den Rest aus, wenn die Summe der Scores über alle Permutationen durch $P$ geteilt wird.
Beispiele
Beispieleingabe 1
10 100000007
Beispielausgabe 1
77379290
Beispieleingabe 2
1000 998244353
Beispielausgabe 2
168695631
Hinweis
Für das erste Beispiel gilt etwa $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$.
Die Summe der Scores über alle $10!$ Permutationen beträgt $277379304$, und der Rest bei Division durch die Primzahl $P = 10^8 + 7$ ist $77379290$, gib also $77379290$ aus. Beachte, dass für diese Eingabe die Primzahl $P$ die $9$-stellige ganze Zahl $10^8 + 7$ ist.