消失之物

题目描述

ftiasch 有 $n$ 个物品, 体积分别是 $w_1,w_2,\dots,w_n$。由于她的疏忽,第 $i$ 个物品丢失了。 “要使用剩下的 $n-1$ 物品装满容积为 $x$ 的背包,有几种方法呢?”——这是经典的问题了。 她把答案记为 $\text{cnt}(i,x)$ ,想要得到所有$i \in [1,n]$, $x \in [1,m]$ 的 $\text{cnt}(i,x)$ 表格。 ![](https://cdn.luogu.com.cn/upload/pic/13426.png)

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3 2
1 1 2

输出样例 #1

11
11
21

说明

【数据范围】 对于 $100\%$ 的数据,$1\le n,m \le 2000$,且 $1\le v_i\le m$。 【样例解释】 如果物品 3 丢失的话,只有一种方法装满容量是 2 的背包,即选择物品 1 和物品 2。 --- $\text{upd 2023.8.11}$:新增加五组 Hack 数据。