题目内容

江岸步道的灯阵调度室要把沿江一列彩灯做成「按闪烁周期」的亮度报表。步道上共有 $n$ 盏灯，从编号 0 依次排到编号 $n-1$。第 $i$ 盏灯出厂时标定的亮度是 $v_i$。值班条例规定：当闪烁周期取定为正整数 $d$ 时，第 $i$ 盏灯落在本周期内的相位等于 $i$ 除以 $d$ 所得的余数，该灯写入报表的贡献等于相位乘上标定亮度。调度室需要 $d=`1`,`2`,\ldots,n$ 每一种周期下的贡献总和，用来对照不同排程。数字可能很大，对 1000000007 取模后再写入报表。

形式化地，把周期 $d$ 的贡献记为 $H(d)$，其定义为

请依次给出 $H(`1`),H(`2`),\ldots,H(n)$ 对 1000000007 取模后的结果。

约束：

• 1 $\le$ $n$ $\le$ 200000
• 0 $\le$ $v_i$ $\le$ 1000000000

输入描述

第一行一个整数 $n$（1 $\le$ $n$ $\le$ 200000），表示彩灯盏数。

第二行 $n$ 个整数 $v_0,v_1,\ldots,v_{n-1}$（0 $\le$ $v_i$ $\le$ 1000000000），表示各盏灯的标定亮度。

输出描述

输出一行 $n$ 个非负整数，依次为 $H(`1`),H(`2`),\ldots,H(n)$ 对 1000000007 取模后的值。

样例1

输入

4
3 1 4 2

输出

0 3 9 15

说明

• $H(`1`)$：任意下标对 1 取余都是 0，总和为 0
• $H(`2`)$：$(0\cdot `3`)+(1\cdot `1`)+(0\cdot `4`)+(1\cdot `2`)=`3`$
• $H(`3`)$：$(0\cdot `3`)+(1\cdot `1`)+(2\cdot `4`)+(0\cdot `2`)=`9`$
• $H(`4`)$：$(0\cdot `3`)+(1\cdot `1`)+(2\cdot `4`)+(3\cdot `2`)=`15`$

样例2

输入

1
8

输出

0

说明

只有一盏编号为 0 的灯。$H(`1`)=(0\bmod `1`)\cdot `8`=`0`$。

样例3

输入

6
2 0 5 1 0 3

输出

0 4 16 16 13 28

说明

• $H(`1`)$ 仍为 0
• $H(`2`)$：余数序列为 $0,1,0,1,0,1$，贡献 $0+0+0+1+0+3=`4`$
• $H(`3`)$：余数序列为 $0,1,2,0,1,2$，贡献 $0+0+10+0+0+6=`16`$
• $H(`4`)$：余数序列为 $0,1,2,3,0,1$，贡献 $0+0+10+3+0+3=`16`$
• $H(`5`)$：余数序列为 $0,1,2,3,4,0$，贡献 $0+0+10+3+0+0=`13`$
• $H(`6`)$：下标都小于 6，贡献就是 $\sum i\cdot v_i=`28`$