【POJ Challenge】消失之物

ftiasch 有 $N$ 个物品，体积分别为 $W_1,W_2,\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$ 的矩阵，其中第 $i$ 行第 $x$ 列表示 $Count(i,x)$ 的末位数字。

样例输入

3 2
1 1 2

样例输出

11
11
21

样例解释

当物品 $3$ 丢失时，只有一种方案能够装满容积为 $2$ 的背包，即选择物品 $1$ 和物品 $2$。

数据范围

• $1\le N\le 2000$；
• $1\le M\le 2000$。

来源与许可

本题为 POJ Challenge 试题「消失之物」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 2
1 1 2

输出

11
11
21