양의 정수 $N$과 소수 $P$가 주어진다. $1, 2, \cdots, N$의 순열 $(a_1, a_2, \cdots, a_N)$에 대하여, 그 점수 $f(a)$를 다음과 같이 정의한다.

$$f(a) = \max\{i a_i \mid i = 1, 2, \cdots, N\}$$

모든 순열에 대한 점수의 합을 $P$로 나눈 나머지를 구하시오.

입력

첫 번째 줄에는 $N$과 $P$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^4$, $10^8 \le P < 10^9$, $P$는 소수)

출력

모든 순열에 대한 점수의 합을 $P$로 나눈 나머지를 출력하시오.

예제

입력 1

10 100000007

출력 1

77379290

입력 2

1000 998244353

출력 2

168695631

참고

첫 번째 예제에서, 예를 들어 $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$이다. $10!$개의 모든 순열에 대한 점수의 합은 $277379304$이며, 이를 소수 $P = 10^8 + 7$로 나눈 나머지는 $77379290$이므로 $77379290$을 출력한다. 이 입력에서 소수 $P$는 9자리 정수 $10^8 + 7$임을 유의하라.