Total Waiting Time for Handmade Items

Each time, the employee works on the order at the front of the queue for 1 hour; if the order is finished it is delivered, otherwise it goes to the back of the queue. Compute the sum of every customer's waiting time from the start until they receive their order, modulo 10⁹.

输入格式

The first line contains N (1..100000), and the second line contains N preparation times (1..10000).

输出格式

Output a single integer, the answer.

样例 1

输入：

3
3 1 2

输出：

13

样例 2

输入：

4
1 2 3 4

输出：

24

样例 3

输入：

3
7 7 7

输出：

60

样例说明

Example 1: the completion times are 6, 2, 5, summing to 13.

Example 2: the completion times are 1, 5, 8, 10, summing to 24.

Example 3: after 6 full rounds totaling 18 hours, the orders finish at hours 19, 20, and 21 in turn, summing to 60.