题目描述

ftiasch 有 $n$ 个物品，体积分别是 $w_1, w_2, \dots, w_n$。由于她的疏忽，第 $i$ 个物品丢失了。
"要使用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法呢？"——这是经典的问题了。
她把答案记为 $\operatorname{cnt}(i, x)$，想要得到所有 $i \in [1, n]$，$x \in [1, m]$ 的 $\operatorname{cnt}(i, x)$ 表格。

输入格式

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

输出格式

输出一个 $n \times m$ 的矩阵，第 $i$ 行包含 $m$ 个数字，依次表示 $\operatorname{cnt}(i, 1), \operatorname{cnt}(i, 2), \dots, \operatorname{cnt}(i, m)$ 的末位数字（即对 $10$ 取模的结果），数字之间不留空格。

样例

3 2
1 1 2

11
11
21

样例解释

• 如果物品 $3$ 丢失，剩下物品 $1$ 和 $2$（体积均为 $1$）。
  要装满容积 $1$ 的背包，可以选择物品 $1$ 或物品 $2$，共 $2$ 种方法，末位为 $2$；
  要装满容积 $2$ 的背包，必须同时选物品 $1$ 和 $2$，共 $1$ 种方法，末位为 $1$。
  因此第三行输出 21。
• 如果物品 $1$ 丢失，剩下物品 $2$（体积 $1$）和物品 $3$（体积 $2$）：
  装满容积 $1$ 只有选物品 $2$ 这 $1$ 种方法；装满容积 $2$ 可以选择物品 $3$，共 $1$ 种方法，末位均为 $1$，输出 11。
• 物品 $2$ 丢失的情况与物品 $1$ 丢失对称，也输出 11。

数据范围

• $1 \le n, m \le 2000$，且 $1 \le w_i \le 2000$。
• 注意：即使多个物品体积相同，它们也视为不同的物品，选择不同的物品算作不同的方案。
• 本题答案可能很大，你只需要输出方案数对 $10$ 取模的末位数字。