На Новый год фермер Джон решил подарить своим коровам праздничное бинарное дерево поиска (БДП)!
Чтобы сгенерировать БДП, ФД начинает с перестановки a = {a[1]
, a[2]
,..., a[n]
} целых чисел 1 ... n, где n ≤ 300. Затем он запускает следующий псевдокод с аргументами 1 и n.
Например, перестановка {3, 2, 5, 1, 4} генерирует следующее БДП:
Пусть d[i](a)
обозначает глубину узла i в дереве, соответствующего a, что означает количество узлов на пути от a[i]
до корня. В приведенном выше примере d[4](a)
= 1, d2(a)
= d[5](a)
= 2, и d[1](a)
= d[3](a)
= 3..
Количество инверсий a равно количеству пар целых чисел (i, j) таких, что 1 ≤ i < j ≤ n и a[i]
> a[j]
. Коровы знают, что a, которое ФД будет использовать для генерации БДП, имеет ровно k инверсий (0 ≤ k ≤ n * (n − 1) / 2). Для всех a, удовлетворяющих этому условию, вычислить остаток от деления ∑a d[i](a)
на m для каждого 1 ≤ i ≤ n.
Единственная строка состоит из трех целых чисел n, k и m. m является простым числом в диапазоне [10^8
, 10^9
+ 9].
Выведите n целых чисел, равных ∑a d[i](a)
(mod m) для каждого 1 ≤ i ≤ n.
Единственной перестановкой будет a = {1, 2, 3}.
Имеются две перестановки a = {1, 3, 2} и a = {2, 1, 3}.