题目描述

有 $n$ 个物品, 体积分别是 $w_1,w_2,\dots,w_n$。每个物品可以使用无限次。

现在，第 $i$ 个物品丢失了。

• 要使用剩下的 $n-1$ 物品 恰好装满 容积为 $x$ 的背包，有几种方法呢？。

输入格式

第一行两个整数 $n,m$，表示物品的数量和最大的容积。 第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示每个物品的体积。

输出格式

输出一个 $n \times m$ 的矩阵，第 $i$ 行第 $j$ 列的数字代表去掉第 $i$ 个物品后，剩余 $n-1$ 个物品凑出容量恰好为 $j$ 的方案。

由于方案数较多，你只需要输出方案的个位数。

3 2
1 1 2

12
12
23

提示

数据范围

• 对于 $50\%$ 的数据，$1\le n,m \le 200$，且 $1\le v_i\le m$。

• 对于 $100\%$ 的数据，$1\le n,m \le 2000$，且 $1\le v_i\le m$。

样例解释

如果物品 $3$ 丢失的话，有三种方法装满容量是 $2$ 的背包

• 选择物品 $1$ 和物品 $2$。
• 选择两个物品 $1$。
• 选择两个物品 $2$。