当前没有测试数据。

消失之物

题目描述

小明有$n$个物品，体积分别是$w_{1}$，$w_{2}$，$\cdots$，$w_{n}$。由于他的疏忽，第$i$个物品丢失了。

"要使用剩下的$n-1$物品装满容积为$x$的背包，有几种方法呢？"——这是经典的问题了。

他把答案记为$cnt(i,x)$，想要得到所有$i \in [1,n]$，$x \in [1,m]$的$cnt(i,x)$表格。

输入格式

第一行两个整数$n$，$m$，表示物品的数量和最大的容积。

第二行$n$个整数$w_{1}$，$w_{2}$，$\cdots$，$w_{n}$，表示每个物品的体积。

输出格式

输出一个$n \times m$的矩阵，表示$cnt(i,x)$的末位数字。

数据范围与提示

对于$100\%$的数据，$1 \leq n,m \leq 2000$。

样例

3 2
1 1 2

11
11
21