Busy Beaver는 프로그래밍을 포기하고 현대 미술을 시작하기로 했습니다! Busy Beaver는 페인트가 묻은 두 개의 토큰을 가지고 있습니다. 그는 다음과 같은 방식으로 무향 그래프를 색칠하려고 합니다.

• 처음에는 모든 정점이 색칠되어 있지 않습니다. 먼저, Busy Beaver는 하나의 토큰을 정점 1에, 다른 하나를 정점 2에 놓습니다.
• 그 후, 그는 그래프의 간선을 따라 토큰을 이동시킵니다. 토큰이 정점 위에 놓일 때마다 해당 정점은 색칠됩니다. (정점 1과 2는 처음에 색칠된 상태로 시작한다는 점에 유의하세요.)
• 과정 중 어느 시점에서도 두 토큰이 간선으로 연결되지 않도록 하면서 모든 정점을 색칠할 수 있다면, 그 그래프를 예술적(artistic)이라고 부릅니다.

$N$개의 정점을 가진 예술적인 무향 그래프의 개수를 구하세요. 답이 클 수 있으므로 소수 $P$로 나눈 나머지를 출력하세요.

입력

각 테스트 케이스의 유일한 줄에는 두 정수 $N$과 $P$가 주어집니다 ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$). $P$는 소수입니다.

출력

$N$개의 정점을 가진 예술적인 무향 그래프의 개수를 $P$로 나눈 나머지를 출력하세요.

예제

입력 1

2 799999999

출력 1

1

입력 2

3 998244853

출력 2

2

입력 3

1984 998244853

출력 3

424428556

참고

첫 번째 테스트 케이스에서, 두 개의 정점과 간선이 없는 그래프가 유일한 예술적 그래프입니다. 두 번째 테스트 케이스에서, 아래의 처음 두 그래프는 예술적입니다. 마지막 그래프는 정점 3을 색칠하는 것이 불가능하기 때문에 예술적이지 않습니다.

(왼쪽부터: 예술적인 그래프 1, 예술적인 그래프 2, 예술적이지 않은 그래프)