Number of DP schemes

 A man came to buy melons .
“ cronies , How much is this melon per kilo ”
“ Two yuan a catty ”
“What's up, This melon skin is made of gold , Or melon particles are made of gold ”

Zhinai came to the fruit stall to buy melons , Fruit stands are selling N Different watermelons , The first i The weight of a watermelon is wi​. Zhinai can choose to buy a whole melon or split the melon to buy half a melon for each melon , The weight of half a melon is wi/2.

That is to say, for every watermelon , Zhinai has three different decisions ：

1. Buy a whole weight of wi​ Watermelon of
2. Split the melon , Buy half a weight of wi/2​​ Watermelon of
3. Do not purchase

To simplify the topic , We guarantee that the weight of all melons is a positive even number .

Now zhinai wants to know , If he wants to buy watermelon, the weight and are k=1,2,3...M when , How many plans are there to buy watermelon , Because these figures may be very large , Please output the number of scheme pairs 10^9+7 The result after taking the remainder .

Input description :

Enter two integers on the first line N,M(0≤N≤10^3,1≤M≤10^3), Each represents the number of watermelons N, And the upper limit of the weight of the query is M.

if N Not for 0, Next line N A positive even number wi(2≤wi≤2×10^3) Represents the weight of each watermelon .

Output description :

 Output one line M A digital , It means the weight of watermelon purchased and k=1,2,3...M when , How many plans are there to buy watermelon , Because these figures may be very large , Please output the number of scheme pairs 10^9+7 The result after taking the remainder .

Example 1

Input

Copy 3 6 8 2 4

3 6
8 2 4

Output

Copy 1 2 1 3 2 3

1 2 1 3 2 3

explain

The purchase weight and is 1 Watermelon in total 1 Kind of plan ：

①、2 Split No. watermelon and buy half .

The purchase weight and is 2 Watermelon in total 2 Kind of plan ：

①、 Direct purchase 2 Watermelon No .

②、3 Split No. watermelon and buy half .

The purchase weight and is 3 Watermelon in total 1 Kind of plan ：

①、2 Split the No. 1 watermelon and buy half, plus 3 Split No. watermelon and buy half .

The purchase weight and is 4 Watermelon in total 3 Kind of plan ：

①、1 Split No. watermelon and buy half .

②、 Direct purchase 2 Watermelon No , Plus 3 Split No. watermelon and buy half .

③、 Direct purchase 3 Watermelon No .

The purchase weight and is 5 Watermelon in total 2 Kind of plan ：

①、2 Split watermelon No. 1 and buy half of it directly 3 Watermelon No .

②、2 Split the No. 1 watermelon and buy half, plus 1 Split No. watermelon and buy half .

The purchase weight and is 6 Watermelon in total 3 Kind of plan ：

①、 Direct purchase 2 Watermelon No , Plus direct purchase 3 Watermelon No .

②、1 Split No. watermelon and buy half , Plus direct purchase 2 Watermelon No .

③、1 Split No. watermelon and buy half , Plus 3 Split No. watermelon and buy half .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1010];
ll dp[1010];
ll n,m;
const ll M=1e9+7;
int main()
{
	cin>>n>>m;
	memset(dp,0,sizeof(dp));dp[0]=1;
	for(ll i=1;i<=n;i++){cin>>a[i];}

  for(ll i=1;i<=n;i++){
	for(ll j=m;j>=1;j--){
			if(j>=a[i])dp[j]=(dp[j]+dp[j-a[i]])%M;
			if(j>=a[i]/2)dp[j]=(dp[j]+dp[j-a[i]/2])%M;
		}
	}
	
	for(ll i=1;i<=m;i++)
	cout<<dp[i]%M<<' ';
	return 0;
}