Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $[l, r]$, where $l, r$ are two integers with $1 \le l \le r \le n$. This indicates the subsegment where $l-1$ elements from the beginning and $n-r$ elements from the end are deleted from the sequence.

For a permutation $p_1, p_2, \ldots, p_n$, we define a framed segment as a subsegment $[l,r]$ where $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$. For example, for the permutation $(6, 7, 1, 8, 5, 3, 2, 4)$ some of its framed segments are: $[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$. In particular, a subsegment $[i,i]$ is always a framed segments for any $i$ between $1$ and $n$, inclusive.

We define the happiness of a permutation $p$ as the number of pairs $(l, r)$ such that $1 \le l \le r \le n$, and $[l, r]$ is a framed segment. For example, the permutation $[3, 1, 2]$ has happiness $5$: all segments except $[1, 2]$ are framed segments.

Given integers $n$ and $m$, Jongwon wants to compute the sum of happiness for all permutations of length $n$, modulo the prime number $m$. Note that there exist $n!$ (factorial of $n$) different permutations of length $n$.


-----Input-----

The only line contains two integers $n$ and $m$ ($1 \le n \le 250\,000$, $10^8 \le m \le 10^9$, $m$ is prime).


-----Output-----

Print $r$ ($0 \le r < m$), the sum of happiness for all permutations of length $n$, modulo a prime number $m$.


-----Examples-----
Input
1 993244853

Output
1

Input
2 993244853

Output
6

Input
3 993244853

Output
32

Input
2019 993244853

Output
923958830

Input
2020 437122297

Output
265955509



-----Note-----

For sample input $n=3$, let's consider all permutations of length $3$:  $[1, 2, 3]$, all subsegments are framed segment. Happiness is $6$.  $[1, 3, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$.  $[2, 1, 3]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$.  $[2, 3, 1]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$.  $[3, 1, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$.  $[3, 2, 1]$, all subsegments are framed segment. Happiness is $6$. 

Thus, the sum of happiness is $6+5+5+5+5+6 = 32$.

Difficulty: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))

fact = [1]

for i in range(1, n + 1):
    fact.append((fact[-1] * i) % m)
    
out = 0

for size in range(1, n + 1):
    out += fact[size] * (n - size + 1) ** 2 * fact[n - size]
    out %= m

print(out)


input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())

n, MOD = MIS()
ans = 0
fac = [1]
for i in range(1, n+2): fac.append(fac[-1] * i % MOD)
for d in range(1, n+1):
    ans+= (n-d+1)**2 * fac[d] * fac[n-d]
    ans%= MOD
print(ans)

n, p = list(map(int,input().split()))
sil = [1] * 300000
sil[0] = 1
sil[1] = 1
for i in range(2,300000):
	sil[i] = (sil[i-1]*i)%p
wyn = 0
for i in range(n):
	wyn = (wyn + (n-i)*sil[n-i]*sil[i+1])%p
print(wyn)