Consider an array, , of length . We can split into contiguous segments called pieces and store them as another array, . For example, if , we have the following arrays of pieces:
We consider the value of a piece in some array to be , and we consider the total value of some array to be the sum of the values for all pieces in that . For example, the total value of is .
Given , find the total values for all possible 's, sum them together, and print this sum modulo on a new line.
The first line contains a single integer, , denoting the size of array .
The second line contains space-separated integers describing the respective values in (i.e., ).
Print a single integer denoting the sum of the total values for all piece arrays ('s) of , modulo .
Sample Input 0
1 3 6
Sample Output 0
Given , our piece arrays are:
When we sum all the total values, we get . Thus, we print the result of on a new line.
Sample Input 1
4 2 9 10 1
Sample Output 1