In several of the future tasks we'll need a way to check whether some array is correct or not. Instead of comparing its length and all of its values with some precalculated sample, we'll use the concept of checksum.

This task with array for which checksum should be calculated. Perform calculation as follows: for each element of
an array (starting from beginning) add this element to `result`

variable and multiply this sum by `113`

- this new
value taken by modulo `10000007`

should become the next value of `result`

, and so on.

Read the article on checksum for detailed description of this algorithm. An example of calculation also could be found there.

For input data you will be given the length of an array in the first line, then array values themselves in the second line, separated by spaces. As an output you need to give only calculated checksum. Example:

```
input data:
6
3 1 4 1 5 9
answer:
8921379
```

All input values are between `0`

and `1,000,000,000`

- be sure to take care of possible overfow in progress of
calculations.

You need to login to get test data and submit solution.