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]
,..., a[n]
} of the integers 1...n, where n ≤ 300. He then runs the following pseudocode with arguments 1 and n.
For example, the permutation {3, 2, 5, 1, 4} generates the following BST:
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, d2(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 ≤ i < j ≤ 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 ≤ k ≤ n * (n − 1) / 2). Over all a satisfying this condition, compute the remainder when ∑a d[i](a)
is divided by m for each 1 ≤ i ≤ n.
The only line consists of three space-separated integers n, k and m. m will be a prime number in the range [10^8
, 10^9
+ 9].
Print n integers denoting ∑a d[i](a)
(mod m) for each 1 ≤ i ≤ n.
Here, the only permutation is a = {1, 2, 3}.
Here, the two permutations are a = {1, 3, 2} and a = {2, 1, 3}.