Vous disposez d'un entier positif $N$ et d'un nombre premier $P$. Pour une permutation $(a_1, a_2, \dots, a_N)$ de $1, 2, \dots, N$, on définit son score $f(a)$ comme suit :

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

Trouvez le reste de la division de la somme des scores sur toutes les permutations par $P$.

Entrée

La première ligne contient $N$ et $P$ dans cet ordre, séparés par des espaces. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ est premier)

Sortie

Affichez le reste de la division de la somme des scores sur toutes les permutations par $P$.

Exemples

Entrée 1

10 100000007

Sortie 1

77379290

Remarque

Pour le premier exemple, par exemple, $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$. La somme des scores sur toutes les $10!$ permutations est $277379304$, et le reste de la division par le nombre premier $P = 10^8 + 7$ est $77379290$, donc affichez $77379290$. Notez que pour cette entrée, le nombre premier $P$ est l'entier à 9 chiffres $10^8 + 7$.

Entrée 2

1000 998244353

Sortie 2

168695631