Min酱要旅行

Time Limit: 8000 ms

Memory Limit: 65535 KB

Description

从前有个富帅叫做Min酱,他很喜欢出门旅行,每次出门旅行,他会准备很大一个包裹以及一大堆东西,然后尝试各种方案去塞满它。 然而每次出门前,Min酱都会有个小小的烦恼。众所周知,富帅是很讨妹子喜欢的,所以Min酱也是有大把大把的妹子,每次出门都会有一只妹子随行。然而这些妹子总是会非常排斥Min酱准备的众多东西中的一件(也许是因为这件东西是其它妹子送给Min酱的),这件东西Min酱是万万不敢带上的,否则的话……嘿嘿嘿。另外,妹子们嫌Min酱的包裹太丑了,会自带一个包裹去换掉Min酱的包裹。 Min酱是个控制欲很强的人,然而这样一来,Min酱就不知道可以用多少种方案去填充包裹了,所以Min酱很郁闷。 于是Min酱找到了聪明的你,希望你能帮助他解决这些问题。 另外,Min酱是个典型的懒人,他不希望每次带不同的妹子出去都麻烦你,所以他希望你能给出有K1..Kn件物品,第i件不能带并且包裹大小为1..M的所有方案数。

Input

可能有多组数据。对于每一组数据: 第一行,两个整数n,m,分别表示物品数量和妹子带的包裹的最大容积。 第二行,n个整数,分别表示物品ki的体积。

1<=n,m<=2300,ki<=1000

Output

对于每一组数据,输出一个n*m的矩阵,第i行j列表示包裹容积为j,不能带i号物品时,装满包裹的方案总数。 为了美观起见,我们只保留方案数的个位。

Sample Input

3 2
1 1 2

Sample Output

11
11
21

Hint

Source

“掌赢杯”南京理工大学第六届程序设计大赛网络预选赛

提交代码