Проблеми з зберіганням

Гангстери здійснили успішне пограбування найвідомішого аукціонного дому в місті. Тепер вони перебувають у своєму сховищі, де зберігають вкрадені речі. На щастя, вам вдалося встановити підслуховувальний пристрій у їхньому сховищі. У вас також є особові справи на кожного гангстера, які містять записи їхніх голосів. Ви уважно стежите за подіями, сподіваючись, що це допоможе вам у розслідуванні пограбування.

Кожен гангстер вкрав рівно один предмет, і $i$-й гангстер вкрав $i$-й предмет. Тепер кожен з них намагається покласти свій предмет у загальне сховище, яке може витримати сумарну вагу $k$. Сховище — це невелика кімната, і гангстери кладуть свої предмети по черзі.

Коли гангстер намагається покласти предмет у сховище, але воно не вміщує його (тобто сумарна вага предметів у сховищі перевищить $k$), він злиться і викидає всі предмети зі сховища. При цьому він каже іншим: "$j$ предметів відправляються у сміття!", де $j$ — це кількість предметів у сховищі в момент, коли він спробував покласти свій предмет. У цей момент починається бійка, і подальше зберігання предметів неможливе.

Оскільки у вас встановлено підслуховувальний пристрій у сховищі гангстерів, ви чуєте, скільки предметів гангстер викидає. Також, завдяки вашим особовим файлам, ви можете відрізнити голос кожного гангстера.

Це значно допоможе вашому розслідуванню, якщо ви заздалегідь дізнаєтеся, для всіх можливих значень $j$ і $i$, скільки різних підмножин предметів могло бути у сховищі в момент, коли $i$-й гангстер викидає всі $j$ предметів. Оскільки кількість підмножин може бути великою, виведіть відповідь за модулем $167772161$.

Вхідні дані

Складається з двох рядків. Перший рядок містить два цілих числа $n$ і $k(2\le n\le 400,1\le k\le 400)$ — кількість гангстерів і максимальна вага, яку може витримати сховище. Другий рядок містить $n$ цілих чисел $w_1,w_2,\dots ,w_n$, таких що $(1\le w_i\le k)$ для кожного $1\le i\le n$. Тут $w_i$ — вага предмета, який вкрав $i$-й гангстер.

Вихідні дані

Виведіть $n$ рядків, кожен з яких містить рівно $n-1$ цілих чисел. Значення в $j$-й позиції $i$-го рядка позначає кількість підмножин предметів, що містять рівно $j$ предметів, які можуть поміститися у сховище, але предмет $i$-го гангстера не може бути доданий. Кожне число виводьте за модулем $167772161$.

Приклади