Nhân dịp năm mới, Nông dân John quyết định tặng các cô bò một cây tìm kiếm nhị phân (BST) mang không khí lễ hội!

Để sinh BST, FJ bắt đầu với một hoán vị \(a=\{a_1,a_2,\ldots,a_N\}\) của các số nguyên \(1 \ldots N\), trong đó \(N \leq 300\). Sau đó, ông chạy mã giả sau với hai tham số \(1\) và \(N\).

generate(l,r):
  nếu l > r, trả về cây con rỗng;
  x = argmin_{l <= i <= r} a_i; // chỉ số của a_i nhỏ nhất trong {a_l,...,a_r}
  trả về một BST có x là gốc,
    generate(l,x-1) là cây con trái,
    generate(x+1,r) là cây con phải;

Ví dụ, hoán vị \(\{3,2,5,1,4\}\) sinh ra BST sau:

    4
   / \
  2   5
 / \
1   3

Gọi \(d_i(a)\) là độ sâu của nút \(i\) trong cây tương ứng với \(a\), nghĩa là số nút trên đường đi từ \(a_i\) đến gốc. Trong ví dụ trên, \(d_4(a)=1\), \(d_2(a)=d_5(a)=2\) và \(d_1(a)=d_3(a)=3\).

Số nghịch thế của \(a\) bằng số cặp số nguyên \((i,j)\) sao cho \(1 \leq i<j \leq N\) và \(a_i>a_j\). Những cô bò biết rằng \(a\) mà FJ sẽ dùng để sinh BST có đúng \(K\) nghịch thế (\(0 \leq K \leq \frac{N(N-1)}{2}\)). Xét tất cả các \(a\) thỏa mãn điều kiện này, với mỗi \(1 \leq i \leq N\), hãy tính phần dư khi \(\sum_ad_i(a)\) được chia cho \(M\).

Dữ liệu vào

Dòng duy nhất của dữ liệu vào gồm ba số nguyên \(N\), \(K\) và \(M\), cách nhau bởi dấu cách, theo sau là một ký tự xuống dòng. \(M\) là một số nguyên tố trong phạm vi \([10^8,10^9+9]\).

Dữ liệu ra

In \(N\) số nguyên cách nhau bởi dấu cách, biểu thị \(\sum_ad_i(a)\pmod{M}\) với mỗi \(1 \leq i \leq N\).

Phân nhóm

• Các test 3–4 thỏa mãn \(N \leq 8\).
• Các test 5–7 thỏa mãn \(N \leq 20\).
• Các test 8–10 thỏa mãn \(N \leq 50\).

Ví dụ

3 0 192603497

1 2 3

3 1 144408983

3 4 4

Nguồn

USACO 2019 December Contest, Platinum - Tree Depth: https://usaco.org/index.php?page=viewproblem2&cpid=974

Tác giả: Yinzhan Xu.