새해와 순열

순열이란 $1$부터 $n$까지의 서로 다른 $n$개의 정수를 임의의 순서로 나열한 배열이다. 예를 들어 $[2,3,1,5,4]$는 순열이지만, $[1,2,2]$는 순열이 아니고 ($2$가 두 번 등장한다), $[1,3,4]$도 순열이 아니다 ($n=3$인데 $4$가 들어 있다).

수열 $a$가 수열 $b$의 부분 구간이라는 것은, $b$의 앞에서 몇 개 (0개 또는 전부일 수도 있다)의 원소를 지우고 뒤에서 몇 개 (0개 또는 전부일 수도 있다)의 원소를 지워 $a$를 얻을 수 있다는 뜻이다. 부분 구간을 $[l, r]$로 나타내며, 여기서 $l, r$은 $1 \le l \le r \le n$인 두 정수다. 이는 앞에서 $l-1$개의 원소를, 뒤에서 $n-r$개의 원소를 지운 부분 구간을 가리킨다.

순열 $p_1, p_2, \ldots, p_n$에 대해, 틀린 구간이란 $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$을 만족하는 부분 구간 $[l,r]$을 말한다. 예를 들어 순열 $(6, 7, 1, 8, 5, 3, 2, 4)$의 틀린 구간으로는 $[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$ 등이 있다. 특히 $[i,i]$는 $1$ 이상 $n$ 이하의 모든 $i$에 대해 항상 틀린 구간이다.

순열 $p$의 행복도는 $1 \le l \le r \le n$이고 $[l, r]$이 틀린 구간인 순서쌍 $(l, r)$의 개수로 정의한다. 예를 들어 순열 $[3, 1, 2]$의 행복도는 $5$이며, $[1, 2]$를 제외한 모든 구간이 틀린 구간이다.

정수 $n$과 $m$이 주어질 때, 종원이는 길이 $n$인 모든 순열의 행복도의 합을 소수 $m$으로 나눈 나머지를 구하려고 한다. 길이 $n$인 순열은 $n!$ ($n$의 계승)개 있다.

한 줄에 두 정수 $n$과 $m$이 주어진다. ($1 \le n \le 250\,000$, $10^8 \le m \le 10^9$, $m$은 소수)

길이 $n$인 모든 순열의 행복도의 합을 소수 $m$으로 나눈 나머지 $r$ ($0 \le r < m$)을 출력한다.

예제 입력 $n=3$에 대해 길이 $3$인 모든 순열을 살펴보자:

• $[1, 2, 3]$: 모든 부분 구간이 틀린 구간이다. 행복도는 $6$.
• $[1, 3, 2]$: $[1, 2]$를 제외한 모든 부분 구간이 틀린 구간이다. 행복도는 $5$.
• $[2, 1, 3]$: $[2, 3]$을 제외한 모든 부분 구간이 틀린 구간이다. 행복도는 $5$.
• $[2, 3, 1]$: $[2, 3]$을 제외한 모든 부분 구간이 틀린 구간이다. 행복도는 $5$.
• $[3, 1, 2]$: $[1, 2]$를 제외한 모든 부분 구간이 틀린 구간이다. 행복도는 $5$.
• $[3, 2, 1]$: 모든 부분 구간이 틀린 구간이다. 행복도는 $6$.

따라서 행복도의 합은 $6+5+5+5+5+6 = 32$이다.