题目描述

$\text{ftiasch}$ 有 $N$ 个物品, 体积分别是 ​$W_1,W_2,W_3,\ldots,W_n$​。 由于她的疏忽, 第 $i$ 个物品丢失了。 “要使用剩下的 $N - 1$ 物品装满容积为 $x$ 的背包，有几种方法呢？” -- 这是经典的问题了。

她把答案记为 $Count(i, x)$ ，想要得到所有$1 \le i \le N, 1 \le x \le M$的 $Count(i, x)$ 表格。

输入格式

第$1$行：两个整数 $N$和$M$，物品的数量和最大的容积。

第$2$行： $N$ 个整数 ​$W_1, ​W_2,\ldots, ​W_n$​, 物品的体积。

输出格式

一个 $N\times M$ 的矩阵， $Count(i, x)$​ 的末位数字。

样例

3 2
1 1 2

11
11
21

样例解释

如果物品$3$丢失的话，只有一种方法装满容量是$2$的背包，即选择物品$1$和物品$2$。

数据范围与约定

对于$100\%$的数据：$1 \le N \le 2\times 10​^3，1 \le M\le 2\times 10​^3,W_i\le 2\times 10^3$。