Bead Sort

Bead sort (also called gravity sort) sorts an array of positive integers by threading beads onto vertical rods and letting gravity pull them down. Implementing it on a computer has many difficulties, such as space complexity, but in a realistic physical model it is known to run in roughly $O(\sqrt{n})$ time. Bead sort proceeds exactly as follows.

1. Let $m$ be the largest value in the sequence. Prepare $m$ rods and number them 1 to $m$. Initially the rods lie flat.
2. Divide each rod into $n$ cells, where the length of one cell equals the diameter of a bead. From this point on, write "the $y$-th cell of the $x$-th rod" as $(x,y)$.
3. For each element $a_i$ of the sequence, thread a total of $a_i$ beads, from $(1,i)$ through $(a_i,i)$.
4. Stand all rods up perpendicular to the ground at the same time, with cell 1 at the top. Gravity pulls each bead toward the higher-numbered cells. Then count the beads in the $i$-th cell from the top. These counts match the elements of the sorted array.

Bead sort therefore uses $\displaystyle{\sum \_i{a\_i}}$ beads in total. For an array $a$ of positive integers, let $f(a)$ be the total distance moved by all $\displaystyle{\sum \_i{a\_i}}$ beads when bead sort is run on $a$, measured in cells. Given an array $b$ of length $n$, compute $f(a_i)$ for each $i$ from 1 to $n$, where $a_i=[b_1, b_2, \cdots b_i]$ is the prefix of length $i$. Since the answer can be large, print it modulo $1\,000\,000\,007$.

The first line contains the length of the array $n$ ($1 \le n \le 2 \times 10^5$).

The second line contains the $n$ positive integers $b_1$ through $b_n$, separated by spaces. ($0 < b_i \le 10^9$)

Print $n$ lines. On the $i$-th line, print the value of $f(a_i)$. Since the answer can be large, print it modulo $1\,000\,000\,007$.