Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

J. Sum of max of iai
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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\ |\ 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\leq N\leq 10^4, 10^8\leq P \lt 10^9,P$$$ is prime)

Output

Print the remainder when the sum of the scores over all permutations is divided by $$$P$$$.

Examples
Input
10 100000007
Output
77379290
Input
1000 998244353
Output
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$$$.