Background

For the new year, Farmer John decided to give his cows a festive binary search tree (BST)!

To generate the BST, FJ starts with a permutation \( a = \{a_1, a_2, \ldots, a_N\} \) of the integers \( 1 \ldots N \), where \( N \leq 300 \). He then runs the following pseudocode with arguments \( 1 \) and \( 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;

For example, the permutation \( \{3, 2, 5, 1, 4\} \) generates the following BST:

    4
   / \
  2   5
 / \ 
1   3

Let \( d_i(a) \) denote the depth of node \( i \) in the tree corresponding to \( a \), meaning the number of nodes on the path from \( a_i \) to the root. In the above example, \( d_4(a) = 1 \), \( d_2(a) = d_5(a) = 2 \), and \( d_1(a) = d_3(a) = 3 \).

The number of inversions of \( a \) is equal to the number of pairs of integers \( (i, j) \) such that \( 1 \leq i < j \leq N \) and \( a_i > a_j \). The cows know that the \( a \) that FJ will use to generate the BST has exactly \( K \) inversions \( (0 \leq K \leq \frac{N(N-1)}{2}) \). Over all \( a \) satisfying this condition, compute the remainder when \( \sum_a d_i(a) \) is divided by \( M \) for each \( 1 \leq i \leq N \).

Problem Description

To celebrate the new year, Farmer John decided to give his cows a festive binary search tree (BST)!

To generate this BST, Farmer John starts with a permutation \( a = \{1, 2, \ldots, N\} \) and runs the following pseudocode with parameters \( l \) and \( r \):

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;

For example, the permutation \( \{3, 2, 5, 1, 4\} \) will generate the following BST:

Let \( d_i(a) \) denote the depth of node \( i \) in the BST generated by permutation \( a \). The depth is defined as the number of nodes on the path from this node to the root. In the example above, \( d_4(a) = 1 \), \( d_2(a) = d_5(a) = 2 \), and \( d_1(a) = d_3(a) = 3 \).

The number of inversions in \( a \) is equal to the number of pairs \( (i, j) \) such that \( 1 \leq i < j \leq N \) and \( a_i > a_j \). The cows know that the permutation \( a \) used by Farmer John to generate the BST has exactly \( K \) inversions. For all permutations \( a \) that satisfy this condition, compute the result of \( \sum_a d_i(a) \mod M \) for each \( 1 \leq i \leq N \).

Input Format

The input consists of a single line containing three integers \( N \), \( K \), and \( M \).

Output Format

Output a single line containing \( N \) integers, where the \( i \)-th integer represents \( \sum_a d_i(a) \mod M \). Separate the integers with a space.

Sample Input and Output

Sample Input #1

3 0 192603497

Sample Output #1

1 2 3

Sample Input #2

3 1 144408983

Sample Output #2

3 4 4

Notes/Hints

Sample Explanation 1

For this example, the only permutation that satisfies the condition is \( a = \{1, 2, 3\} \).

Sample Explanation 2

For this example, the two permutations that satisfy the condition are \( a = \{1, 3, 2\} \) and \( a = \{2, 1, 3\} \).

Data Range

For all test cases, \( 1 \leq N \leq 300 \), \( 0 \leq K \leq \frac{N(N-1)}{2} \), and \( M \) is a prime number in the range \( [10^8, 10^9 + 9] \).

For test cases \( 3, 4 \), \( N \leq 8 \);

For test cases \( 5-7 \), \( N \leq 20 \);

For test cases \( 8-10 \), \( N \leq 50 \).

This problem is USACO 2019 December Platinum Problem 3.

见题面 Input 部分

见题面 Output 部分