Saxlama problemləri

Qanqsterlər şəhərin ən məşhur hərrac evini uğurla qarət etdilər və indi oğurladıqları əşyaları sığınacaqlarında saxlayırlar. Xoşbəxtlikdən, siz onların sığınacağına dinləmə cihazı quraşdırmısınız və hər bir qanqsterin səs yazısını ehtiva edən şəxsi işləriniz var. Siz qarətin araşdırılmasına kömək edəcəyinə ümid edərək, baş verənləri diqqətlə izləyirsiniz.

Hər bir qanqster dəqiq bir əşya oğurlayıb və $i$-ci qanqster $i$-ci əşyanı oğurlayıb. İndi hər biri öz əşyasını ümumi anbara yerləşdirməyə çalışır, hansı ki, ümumi çəkisi $k$-ya qədər olan əşyaları saxlaya bilər. Anbar kiçik bir otaqdır və qanqsterlər əşyalarını növbə ilə yerləşdirirlər.

Əgər qanqster əşyasını anbara yerləşdirməyə çalışanda anbar onu qəbul edə bilməzsə (yəni anbardakı əşyaların ümumi çəkisi $k$-dan çox olacaqsa), o, əsəbiləşir və anbardan bütün əşyaları atır. Bu zaman o, digərlərinə deyir: "$j$ əşya zibilə gedir!" burada $j$ — o, əşyasını yerləşdirməyə çalışanda anbarda olan əşyaların sayıdır. Bu anda dava başlayır və əşyaların daha da saxlanması mümkün deyil.

Siz qanqsterlərin anbarına dinləmə cihazı quraşdırdığınız üçün, qanqsterin neçə əşya atdığını eşidirsiniz. Həmçinin, şəxsi işləriniz sayəsində, hər bir qanqsterin səsini ayıra bilirsiniz.

Bu, qarətin araşdırılmasına çox kömək edəcək, əgər siz əvvəlcədən bilsəniz ki, bütün mümkün $j$ və $i$ dəyərləri üçün, $i$-ci qanqster bütün $j$ əşyaları atanda anbarda neçə müxtəlif əşya altmüəyyənliyi ola bilər. Alt kümələrin sayı böyük ola biləcəyi üçün, cavabı $167772161$ modulu ilə verin.

Giriş verilənləri

İki sətirdən ibarətdir. Birinci sətir $n$ və $k(2\le n\le 400,1\le k\le 400)$ — qanqsterlərin sayı və anbarın saxlaya biləcəyi maksimum çəki olan iki tam ədədi ehtiva edir. İkinci sətir $n$ tam ədədi $w_1,w_2,\dots ,w_n$ ehtiva edir, burada $(1\le w_i\le k)$ hər bir $1\le i\le n$ üçün. Burada $w_i$ — $i$-ci qanqsterin oğurladığı əşyanın çəkisidir.

Çıxış verilənləri

$n$ sətir çıxarın, hər biri dəqiq $n-1$ tam ədədi ehtiva edir. $i$-ci sətirin $j$-ci mövqeyindəki dəyər, $i$-ci qanqsterin əşyası əlavə edilə bilməyən, dəqiq $j$ əşyadan ibarət olan əşyaların altmüəyyənliklərinin sayını göstərir. Hər bir ədədi $167772161$ modulu ilə çıxarın.

Nümunələr