JOI 왕국의 축제 2

JOI 왕국에서는 국가 축제가 1년에 한 번 열린다. 축제 기간에는 총 $N$개의 이벤트가 있고, 각 이벤트의 일정은 이미 정해져 있다. $N$개 이벤트의 일정은 다음 조건을 만족하는 길이 $N$의 수열 $a$, $b$로 나타낸다.

• $1$ 이상 $2N$ 이하의 모든 정수가 $a$ 또는 $b$의 원소로 나타난다.
• $a_i < b_i$ ($1 \le i \le N$).
• $a_i < a_{i+1}$ ($1 \le i \le N-1$).

$i$번째 이벤트는 축제 시작 후 $a_i$분에 시작하여 $b_i$분에 끝난다.

참가자는 원하는 이벤트를 고를 수 있다. 다만 일정이 겹치는 두 이벤트에는 함께 참가할 수 없다. (모든 이벤트의 시작 시각과 종료 시각은 서로 다르다.)

JOI 군은 가능한 한 많은 이벤트에 참가하려고 한다. 지난해까지 JOI 군은 컴퓨터에서 다음 절차로 참가할 이벤트를 골랐다.

• $i = 1, 2, \dots, N$에 대해 다음을 이 순서대로 수행한다.
  • $i$번째 이벤트의 일정이 이미 참가하기로 한 이벤트들의 일정과 겹치지 않으면 $i$번째 이벤트에 참가한다. 그렇지 않으면 참가하지 않는다.

그런데 컴퓨터 과학을 공부한 JOI 군은 위 절차가 참가하는 이벤트 수를 반드시 최대로 만들지는 않는다는 것을 알게 되었다. 올해부터 JOI 군은 개선된 알고리즘을 사용한다. 개선된 알고리즘을 사용하면 JOI 군은 참가하는 이벤트 수를 최대로 만들 수 있다.

JOI 군은 개선된 알고리즘이 더 많은 이벤트에 참가하게 되는 경우의 수를 알고 싶어 한다.

정수 $N$과 큰 소수 $P$가 주어질 때, 개선된 알고리즘이 더 많은 이벤트를 얻게 되는 일정 수열 쌍 $a$, $b$의 개수를 $P$로 나눈 나머지를 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

$N$ $P$

표준 출력에 한 줄을 출력한다. 출력하는 값은 개선된 알고리즘이 더 많은 이벤트에 참가하게 되는 $a$, $b$ 수열 쌍의 개수를 $P$로 나눈 나머지이다.

• $1 \le N \le 20\,000$.
• $10^8 < P < 10^9$.
• $P$는 소수이다.
• 주어지는 값은 모두 정수이다.