시간 제한메모리 제한제출정답맞힌 사람정답 비율
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