Hash the Array
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.
Examples
Input | Output |
5
1 2 3 7 10 | 210881767 |
5
7 1 2 3 10 | 168239460 |
1
1 | 127 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB