Migrated from Lutece 1743 01背包计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你有若干种不同的物品，其中体积为$i$的物品有$a_i$种，每种物品有$1$个，求选取物品恰好装满总体积为$1到n$的背包的方案数.

Input

第一行一个整数$n$.($1 \leq n \leq 10^5$)

接下来一行有$n$个整数，分别表示$a_i$($1 \leq a_i \leq 10^5$)

Output

输出$n$行，分别表示从$1$到$n$时的答案，只需输出其在$\text{mod } 10^9 +7$意义下的值即可

Samples

5
2 3 4 1 5

2
3
10
9
19

Resources

Prepared by xiper