Maximum Subsegment Sum is a classical problem. When Rikka first saw this problem, she was still an outsider of competitive programming, and now, she has become a problem setter of this grand event.
Therefore, Rikka decides to set a problem about Maximum Subsegment Sum. Given an array x of length m, its maximum subsegment sum is defined as:

Now, given an integer array A of length n, Rikka wants you to calculate the sum of the maximum subsegment sums of all subsegments of A, i.e.

The first line contains a single integer .
The second line contains n integers .

Output a single line with a single integer, the answer. The answer can be very large, therefore, you are only required to output the answer modulo .
More formally, suppose the answer is x, you are required to find the smallest non-negative integer y satisfying  for some integer k.

5
1 -1 1 -1 1

11

5
1 -2 3 -4 5

39

10
1 -3 -5 7 -9 10 8 -6 -4 2

555

4
-1 -2 -3 -4

18446744073709551596