子集和（四）

题目描述

子集和问题是指，给定 $n$ 个数字 $a_1,a_2,\cdots ,a_n$ ，再给定一个目标 $t$，有多少种方法，能够选出一些数字，使得它们的和等于 $t$。注意每个数字可以重复选择多次。

小爱希望计算一些带有限制的子集和问题，她想知道，如果规定不能选择 $a_i$，那么还有多少种方法，可以选出一些数字，使得它们的和等于目标 $t$？

输入格式

第一行：两个整数表示 $n$ 与 $t$。

第二行：$n$ 个整数表示 $a_1,a_2,\cdots ,a_n$；输入数据保证对任意 $i\ne j$ 有 $a_i\ne a_j$。

输出格式

共 $n$ 行，每行一个数，表示有多少种方法，在禁止选择 $a_i$ 的条件下，子集和问题的答案。由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

数据范围

对于 $30\mathrm{\%}$ 的数据，$1\le n\le 20$；

对于 $60\mathrm{\%}$ 的数据，$1\le n\le 300$；

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 5000$；

$1\le a_i\le 10000$;

$1\le t\le 10000$；

样例数据

输入：

3 16
1 5 10

输出：

0
2
4

说明：

不用1不可能
不用5的方案为 1*16, 1*6+10*1 
不用10的方案为 1*16, 1*11+5*1, 1*6+5*2, 1*1+5*3