트리 깊이

새해를 맞아 Farmer John은 소들에게 축제 분위기의 이진 탐색 트리(BST)를 선물하기로 했다!

BST를 만들기 위해 FJ는 먼저 정수 $1\ldots N$의 순열 $a=\{a_1,a_2,\ldots,a_N\}$에서 시작한다. 여기서 $N\le 300$이다. 그다음 인수 $1$과 $N$으로 아래 의사코드를 실행한다.

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

예를 들어 순열 $\{3,2,5,1,4\}$는 다음과 같은 BST를 만든다.

    4
   / \
  2   5
 / \ 
1   3

$d_i(a)$는 $a$에 대응하는 트리에서 노드 $i$의 깊이, 즉 $a_i$에서 루트까지 가는 경로 위의 노드 수를 뜻한다. 위 예에서 $d_4(a)=1, d_2(a)=d_5(a)=2$이고 $d_1(a)=d_3(a)=3$이다.

$a$의 역전 수는 $1\le i<j\le N$이고 $a_i>a_j$인 정수 쌍 $(i,j)$의 개수와 같다. 소들은 FJ가 BST를 만들 때 사용할 $a$의 역전 수가 정확히 $K$라는 것을 알고 있다 $(0\le K\le \frac{N(N-1)}{2})$. 이 조건을 만족하는 모든 $a$에 대해, 각 $1\le i\le N$마다 $\sum_a d_i(a)$를 $M$으로 나눈 나머지를 구하시오.

입력의 유일한 줄에는 공백으로 구분된 세 정수 $N, K, M$이 주어지고 그다음에 줄 바꿈이 온다. $M$은 $[10^8,10^9+9]$ 범위의 소수이다.

각 $1\le i\le N$에 대해 $\sum_a d_i(a)\pmod{M}$을 나타내는 $N$개의 정수를 공백으로 구분해 출력한다.