Description

子集和问题是指，给定 n个数字a1,a2,⋯,an，再给定一个目标 t，有多少种方法，能够选出一些数字，使得它们的和等于 t。注意每个数字可以重复选择多次。 小爱希望计算一些带有限制的子集和问题，她想知道，如果规定不能选择ai，那么还有多少种方法，可以选出一些数字，使得它们的和等于目标 t？

Format

Input

第一行：两个整数表示 n 与 t。 第二行：n 个整数表示a1,a2,⋯,an输入数据保证对任意 i!=j 有 ai!=aj。

Output

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

Samples

3 16
1 5 10

0
2
4

Limitation

对于 30% 的数据，1≤n≤20； 对于 60% 的数据，1≤n≤300； 对于 100% 的数据，1≤n≤5000； 1≤ai≤10000； 1≤t≤10000；