Migrated from Lutece 1729 序列计数

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

有若干张颜色不同的骨牌，其中大小为$1 \ast i$的骨牌有$a_i$种，每种骨牌都可以无限量使用。用骨牌不重叠地铺满一排$1 \ast n$的方格，共有多少种方法？

Input

第一行包含一个整数$n$

接下来一行包含$n$个整数，分别表示$a_i$

数据保证：

• $1 \leq n,a_i \leq 10^5$

Output

输出$n$个数表示$(1 \ast i)$时的答案，因为答案可能较大，因此只需要输出其在$\text{mod } 10^9 + 7$意义下的值即可.

Samples

5
1 8 7 4 6

1 9 24 107 372

Resources

Prepared by xiper