수수께끼의 … 주최자

마침내 리카는 효율적인 교통을 만들면서도 돈이 적게 드는 훌륭한 설계를 얻었다. 하지만 리카는 진부한 관리들이 그것을 받아들일지 신경 쓰지 않았다. LCR은 순결한 미소와 화환, 하얀 드레스를 걸치고 오래전부터 그녀의 뒤에 서 있었기 때문이다. 그 미소에 서서히 마음을 가라앉힌 소녀들은 손을 내밀어 여정을 시작했다. 낭만적인 만남 끝에 그들은 서북공업대학 부속중학교의 자습실에 도착했다.

화이트보드와 종이에 적힌 공식들은 리카에게 (물론 공부에 대한) 기억을 되살려 주었고, 그래서 그녀는 지금 LCR에게 함께 게임을 하자고 부탁한다 (조합론을 복습하기 위해서다).

LCR은 $n$차 순열을 하나 가지고 있고 리카는 그것을 맞히려 한다. 처음에 리카는 $n$차 순열의 집합을 하나 골라야 한다. 그다음 LCR이 몇 번의 질의를 한다. 매번 LCR은 구간 $[L, R]$ ($1\le L\le R\le n$)을 주고, 리카는 고른 각 순열마다 그 구간이 그 안에서 연속인지 (아래 문단에서 정의한다) 답한다. 마지막에 리카는 고른 순열 중 LCR의 원래 순열과 모든 질의에 대한 답이 같은 것이 하나라도 존재하면 게임에서 이긴다.

리카는 게임을 반드시 이기려면 순열을 최소 몇 개 골라야 하는지 궁금해한다. 앞으로의 게임을 위해 그녀는 $N$ 이하의 모든 양의 정수 $n$에 대한 답이 필요하다. 정확한 값은 너무 클 수 있으므로 어떤 소수 $P$로 나눈 나머지만 구하면 된다.

구간 $[L, R]$이 $n$차 순열 $p$에서 연속이라는 것은 다음 조건을 만족하는 세 정수 $x, y, z$가 존재하지 않는다는 뜻이다. $1\le x, y, z\le n$, $p_x<p_y<p_z$, $x, z \in [L, R]$, $y \notin [L, R]$. 여기서 $p_i$ ($i = 1, 2, \dots, n$)는 $[1, n]$ 안의 정수이고, 순열 $p$의 $i$번째 원소를 뜻한다.

첫 줄에 두 정수 $N$ ($1\le N\le 5000$), $P$ ($1\le P < 2^{30}$, $\exists k\in \mathbb{N}, P=k\cdot 2^{14}+1$)가 공백으로 구분되어 주어진다. 각각 순열 차수의 최댓값과 나눗수다. $P$는 소수임이 보장된다.

$N$개의 줄을 출력한다. $n = 1, 2, \dots, N$에 대해 $n$번째 줄에는 리카가 $n$차 순열에 대해 골라야 하는 순열 개수의 최솟값을 $P$로 나눈 나머지를 출력한다.

$n=3$이면 순열은 $6$개, 가능한 질의는 $6$개다. 이 상황에서 리카의 응답은 다음과 같다.

답은 $3$이다. 예를 들어 리카가 $(1, 2, 3), (1, 3, 2), (2, 1, 3)$을 고르면, LCR이 어떤 순열을 가지고 있든 고른 순열 중 LCR의 순열과 모든 질의에 대한 답이 같은 것이 존재한다.