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={a1,a2,…,aN} of the integers 1…N, where N≤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 di(a) denote the depth of node i in the tree corresponding to a, meaning the number of nodes on the path from ai to the root. In the above example, d4(a)=1,d2(a)=d5(a)=2, and d1(a)=d3(a)=3.
The number of inversions of a is equal to the number of pairs of integers (i,j) such that 1≤i<j≤N and ai>aj. The cows know that the a that FJ will use to generate the BST has exactly K inversions (0≤K≤N(N−1)2). Over all a satisfying this condition, compute the remainder when ∑adi(a) is divided by M for each 1≤i≤N.
Input Format
The only line of input consists of three space-separated integers N,K, and M, followed by a new line. M will be a prime number in the range [108,109+9].
Output Format
Print N space-separated integers denoting \sum_ad_i(a)\pmod{M} for each 1\le i\le N.
Batching
- Test cases 3-4 satisfy N\le 8.
- Test cases 5-7 satisfy N\le 20.
- Test cases 8-10 satisfy N\le 50.
Sample Input 1
3 0 192603497
Sample Output 1
1 2 3
Here, the only permutation is a=\{1,2,3\}.
Sample Input 2
3 1 144408983
Sample Output 2
3 4 4
Here, the two permutations are a=\{1,3,2\} and a=\{2,1,3\}.
Problem credits: Yinzhan Xu