题目描述

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

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

输入格式

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

输出格式

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

3 16
1 5 10

0
2
4

样例解释 1

不用1不可能 不用5的方案为 116, 16+101 不用10的方案为 116, 111+51, 16+52, 11+53

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 300$；
• 对于 $100\%$ 的数据，$1\leq n\leq 5000$；
• $1\leq a_i\leq 10000$；
• $1\leq t\leq 10000$；