Problem Description

Takahashi receives a sequence from his mother every year on his birthday. He enjoys calculating the number of swaps in bubble sort for the sequence he receives each year.

However, this year, his mother is different. She gave him a compressed version of a very long sequence to make his task even more enjoyable.

Even Takahashi, who can calculate the number of swaps in bubble sort for a sequence of length $ 10^7 $ in just one second, couldn't handle this sequence.

Your task is to calculate the number of swaps in bubble sort for this sequence modulo $ 10^9+7 $.

Bubble sort is given by the following pseudocode:

```

input: a[1],...,a[N]
for i=1 to N-1
{
for j=1 to N-i
{
if a[j]>a[j+1] swap(a[j],a[j+1])
}
}

The number of swaps in bubble sort is the number of times the swap function is called in the above pseudocode.

The method to obtain the original sequence from the compressed sequence is as follows:

- Initially, the pointer points to the first term of the compressed sequence, and the stack is empty. Repeat the following operations until the pointer goes out of the compressed sequence. The final sequence remaining in the stack is the desired sequence.
- If the value pointed to by the pointer is positive, push a sequence consisting of that single value onto the stack and move the pointer one step forward.
- If the value pointed to by the pointer is $ 0 $, pop the first and second sequences from the top of the stack, concatenate the former to the end of the latter, push the resulting sequence onto the stack, and move the pointer one step forward.
- If the value pointed to by the pointer is negative, pop the top sequence from the stack, repeat it $ |value| $ times, push the resulting sequence onto the stack, and move the pointer one step forward.

For example, the sequence

1 2 3 0 -4 5 0 0 -2

represents the sequence ```

1 2 3 2 3 2 3 2 3 5 1 2 3 2 3 2 3 2 3 5

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ ... $ A_N $

Output Format

Output the number of swaps in bubble sort for the sequence represented by the compressed sequence modulo $ 10^9+7 $.

Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

9
1 2 3 0 -4 5 0 0 -2

Sample Output #1

45
```### Sample Input #2

22
12 35 -901 0 43 73 0 -18 2 6 0 -9 428 0 0 0 -23 8 0 -66 2 0

### Sample Output #2

509114582
```

Notes/Hints

Constraints

• $ N > 0 $
• $ -10^5 ≦ A_i ≦ 10^5 (1 ≦ i ≦ N) $
• The number of $ i $ such that $ A_i ≠ 0 $ does not exceed $ 10^5 $.
• It is guaranteed that the given compressed sequence can be restored to the original sequence by the method described above.
• All inputs are integers.

Partial Points

This problem has partial points.

• If you solve the dataset where the number of non-zero elements in the compressed sequence does not exceed $ 2000 $, you will be awarded $ 50 $ points as partial credit.

见题面 Input 部分

见题面 Output 部分