Shell Necklace

Problem Description

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough. Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love. I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.

Input

There are multiple test cases(no more than $20$ cases and no more than 1 in extreme case), ended by 0. For each test cases, the first line contains an integer $n$, meaning the number of shells in this shell necklace, where $1 \leq n \leq 10^{5}$. Following line is a sequence with $n$ non-negative integer $a_{1},a_{2},…,a_{n}$, and $a_{i} \leq 10^{7}$ meaning the number of schemes to decorate $i$ continuous shells together with a declaration of love.

Output

For each test case, print one line containing the total number of schemes module $313$(Three hundred and thirteen implies the march 13th, a special and purposeful day).

Sample Input

3
1 3 7
4
2 2 2 2
0

Sample Output

14
54

Hint

For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.

Author

HIT

Source

2016 Multi-University Training Contest 1