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.
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.
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).