Counting Ways to Fill a Knapsack

A knapsack can hold items with a total volume of at most $10^5$. Princess Fu is preparing for a stall with n types of goods. Each good has a volume of $v_i$ and is available in an unlimited quantity.

You are given an integer m. For every integer $s$ in the range $[1, m]$, count the number of ways to exactly fill a knapsack of volume $s$ using these goods. Since the answer can be very large, output the result modulo $10^9+7$.

Note: Two ways are considered different if the multiset of items used is different. The order of selection does not matter.

Constraints:

• $1 \leq n \leq 100$
• $1 \leq m \leq 10^5$
• $1 \leq v_i \leq 10^5$

inputFormat

The first line of input contains two integers n and m, separated by a space.

The second line contains n space-separated integers, representing the volumes $v_1, v_2, \ldots, v_n$ of the goods.

outputFormat

Output a single line containing m space-separated integers. The i-th integer (for $1 \leq i \leq m$) should be the number of ways to exactly fill a knapsack of volume $i$ modulo $10^9+7$.

sample

2 5
1 2

1 1 2 2 3