You are given a positive integer $N$ and a prime number $P$.
For a permutation $(a_1, a_2, \cdots, a_N)$ of $1, 2, \cdots, N$, define its score $f(a)$ as follows.
$$f(a) = \max\{ia_i \mid i = 1, 2, \cdots, N\}$$
Find the remainder when the sum of the scores over all permutations is divided by $P$.
Input
The first line contains $N, P$ in this order, separated by spaces. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$ is prime)
Output
Print the remainder when the sum of the scores over all permutations is divided by $P$.
Examples
Sample Input 1
10 100000007
Sample Output 1
77379290
Sample Input 2
1000 998244353
Sample Output 2
168695631
Note
For the first example, for instance, $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$.
The sum of the scores over all $10!$ permutations is $277379304$, and the remainder when this is divided by the prime $P = 10^8 + 7$ is $77379290$, so print $77379290$. Note that for this input, the prime number $P$ is the $9$-digit integer $10^8 + 7$.