题目描述

The gangsters did a very successful robbery of the city's most famous auction house. Now they are safely at their hideout, where they store the stolen items. Luckily, you managed to place a listening device into their hideout. You also have a personal file on each ganger, which contains a recording of their voice. You will listen carefully to what happens next with hope it will help you with the investigation of the robbery.

Each gangster stole exactly one item, the $i$-th gangster stole the $i$-th item. Now each gangster is trying to put his item into the common storage, which can hold a total weight of $K$. The storage is a small room and the gangsters store their items one by one.

When a gangster tries to put an item into the storage but it does not fit, that is the total weight of the items in the storage would exceed $K$, he gets angry and throws all the items in the storage out. While doing this, he tells the others that "$j$ items are going to trash!", where $j$ is the number of items in the storage at the point he tried to store his item. At this point a fight ensues and no more storing will happen.

As you have a listening device in the gangsters' storage, you will hear how much items the gangster throws out. Also, using your personal files, you can tell apart each of the gangster's voices.

Therefore, it would help your investigation greatly if you could know in advance, for all possible values of $j$ and $i$, how many different subsets of items could be in the storage at the moment when the $i$-th gangster throws all the $j$ items out. As the number of subsets can be large, output it modulo $167772161$.

输入格式

The input consists of two lines. The first line contains two integers $N$ and $K$ ($2 \leq N \leq 400$, $1 \leq K \leq 400$), the number of gangsters and the maximum weight that the storage can hold. The second line contains $N$ integers $w_1, w_2, \cdots, w_N$, such that ($1 \leq w_i \leq K$) for each $1 \leq i \leq N$. Here $w_i$ is the weight of item that the $i$-th gangster stole.

输出格式

The output consists of $N$ lines, each line containing exactly $N-1$ integers. The $j$-th value on the $i$-th line contains the number of subsets of items containing exactly $j$ items, such that they fit into the storage but the $i$-th gangster's item can not be added. Each number is modulo $167772161$.

3 3
2 2 1

1 1
1 1
0 0

5 5
1 2 3 4 5

1 1 0 0
2 2 0 0
2 2 0 0
3 3 0 0
4 4 0 0