Ağacın dərinliyi

Yeni il üçün fermer Con inəklərinə bayram ikili axtarış ağacı (İAA) hədiyyə etmək qərarına gəldi!

İAA yaratmaq üçün FC a = {a[1], a[2],..., a[n]} tam ədədlərinin 1 ... n-dən ibarət permutasiyası ilə başlayır, burada n ≤ 300. Sonra o, aşağıdakı psevdokodu 1 və n arqumentləri ilə işə salır.

generate(l,r):
  if l > r, return boş alt-ağac;
  x = argmin_{l <= i <= r} a_i; // {a_l,...,a_r} arasında min a_i indeks
  return İAA x kökdə olmaqla, 
    generate(l,x-1) sol alt-ağac kimi,
    generate(x+1,r) sağ alt-ağac kimi;

Məsələn, {3, 2, 5, 1, 4} permutasiyası aşağıdakı İAA yaradır:

    4
   / \
  2   5
 / \ 
1   3

d[i](a) a-ya uyğun ağacda i düyününün dərinliyini ifadə edir, yəni a[i]-dən kökə qədər olan yol üzərindəki düyünlərin sayını göstərir. Yuxarıdakı nümunədə d[4](a) = 1, d[2](a) = d[5](a) = 2, və d[1](a) = d[3](a) = 3.

a-nın inversiyalarının sayı 1 ≤ i < j ≤ n və a[i] > a[j] olan tam ədəd cütlərinin (i, j) sayına bərabərdir. İnəklər bilirlər ki, FC İAA yaratmaq üçün istifadə edəcəyi a-nın dəqiq k inversiyası var (0 ≤ k ≤ n * (n − 1) / 2). Bu şərti ödəyən bütün a üçün hər bir 1 ≤ i ≤ n üçün ∑a d[i](a)-nın m-ə bölünməsindən alınan qalıq hesablanmalıdır.

Giriş məlumatları

Yeganə sətir üç tam ədəd n, k və m-dən ibarətdir. m [10^8, 10^9 + 9] aralığında sadə ədəddir.

Çıxış məlumatları

Hər bir 1 ≤ i ≤ n üçün ∑a d[i](a) (mod m) bərabər olan n tam ədəd çıxarın.

Nümunə 1

Yeganə permutasiya a = {1, 2, 3} olacaq.

Nümunə 2

İki permutasiya var: a = {1, 3, 2} və a = {2, 1, 3}.