Ti vengono dati un intero positivo $N$ e un numero primo $P$.
Per una permutazione $(a_1, a_2, \cdots, a_N)$ di $1, 2, \cdots, N$, definisci il suo punteggio $f(a)$ come segue.
$$f(a) = \max\{ia_i \mid i = 1, 2, \cdots, N\}$$
Trova il resto della divisione per $P$ della somma dei punteggi su tutte le permutazioni.
Input
La prima riga contiene $N, P$ in quest'ordine, separati da spazi. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ è primo)
Output
Stampa il resto della divisione per $P$ della somma dei punteggi su tutte le permutazioni.
Esempi
Input di esempio 1
10 100000007
Output di esempio 1
77379290
Input di esempio 2
1000 998244353
Output di esempio 2
168695631
Note
Per il primo esempio, ad esempio, $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$.
La somma dei punteggi su tutte le $10!$ permutazioni è $277379304$, e il resto della divisione di questo valore per il numero primo $P = 10^8 + 7$ è $77379290$, quindi stampa $77379290$. Nota che per questo input, il numero primo $P$ è l'intero di $9$ cifre $10^8 + 7$.