시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB222100.000%

문제

$n$ players are playing in an elimination tournament. The tournament is a sequence of $n - 1$ matches. Each match consists of two people playing against each other. One of them loses and is eliminated from the tournament (i.e. he can't participate in any further matches) and the other one wins and is not eliminated. The last match is called the final, because it consists of the only two not eliminated players. No two consecutive matches, none of which is the final, may share a participant.

How many different possible tournaments are there? Two tournaments are considered different if there exists a pair of players which played against each other in one of them but didn't in the other.

Output the correct answer modulo a prime number $m$. Formally, if the actual answer is $y$ and your answer is $x$, it will be considered correct if $-2^{63} \leq x < 2^{63}$ and $x-y$ is divisible by $m$.

입력

The only line contains two integers $n$ and $m$ ($2 \leq n \leq 10^6, 10^6 + 3  \leq m \leq 10^9+9$, $m$ is prime), the number of players and the modulo.

출력

Print a single integer --- the number of possible tournaments modulo $m$.

예제 입력 1

2 1000003

예제 출력 1

1

예제 입력 2

3 756871351

예제 출력 2

3

예제 입력 3

4 79415263

예제 출력 3

12

예제 입력 4

10 62493391

예제 출력 4

37074959

예제 입력 5

228 602495767

예제 출력 5

489051459

예제 입력 6

1000 347390201

예제 출력 6

71907364

예제 입력 7

3228 172329319

예제 출력 7

92438468

예제 입력 8

10000 288002747

예제 출력 8

214265262

예제 입력 9

32228 839393021

예제 출력 9

778284082

예제 입력 10

100000 625953467

예제 출력 10

462027594

예제 입력 11

322228 493329803

예제 출력 11

424612739

예제 입력 12

1000000 1000000009

예제 출력 12

195243062