Given n numbers, you are asked to calculate the total hash of all of those numbers. To compute the hash value for an array of numbers, we can use this formula:

Note that it’s more optimal to calculate the powers of 127 by multiplying the previous power by 127 on every iteration. Also, keep in mind that computing the mod at the end is the same as computing the mod for each element and then summing those together.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).

The next line contains n space-separated integers (0 ≤ ≤ ).

Output

The program should print the resulting hash of the array.