问题文

高桥君每年生日都会从他妈妈那里得到一个数列。由于高桥君喜欢求解冒泡排序的交换次数，所以每年他都会计算出他妈妈给他的数列的冒泡排序交换次数。

但是今年高桥君的妈妈有点不同。她为了让高桥君更加享受求解冒泡排序交换次数的乐趣，给他传递了一个非常长的压缩过的数列。

对于长度为 $10^7$ 的数列的冒泡排序交换次数，即使是可以在1秒内进行目视计算的高桥君，也无法应付这个数列。

你的任务是代替高桥君计算这个数列的冒泡排序交换次数除以 $10^9+7$ 的余数。

冒泡排序是由下面的伪代码描述的算法：

输入: 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])
      }
}

冒泡排序的交换次数是指在上述伪代码中swap被调用的次数。

此外，从压缩列恢复原始数列的方法如下：

• 起初，指针指向压缩列的第一个元素，堆栈为空。重复以下操作直到指针超出压缩列的边界。最后堆栈中剩下的一个数列就是目标数列。
• 如果指针指向的值为正数，则将这个值构成的数列推入堆栈，然后将指针向前移动一个位置。
• 如果指针指向的值为0，则从堆栈中弹出第1个和第2个数列，将第1个数列连接到第2个数列的末尾，然后将结果数列推入堆栈，并将指针向前移动一个位置。
• 如果指针指向的值为负数，则从堆栈中弹出顶部的数列，并将它重复 $|指针指向的值|$ 次后推入堆栈，并将指针向前移动一个位置。

例如，序列

1 2 3 0 -4 5 0 0 -2
```表示数列```plain

1 2 3 2 3 2 3 2 3 5 1 2 3 2 3 2 3 2 3 5
```。

* * *

### 约束条件

*   $N > 0$
*   $\-10^5 ≦ A_i ≦ 10^5(1 ≦ i ≦ N)$
*   不会有超过 $10^5$ 个 $A_i ≠ 0$。
*   压缩列可以通过上述方法保证恢复为原始数列。
*   输入都是整数。

### 输入

输入的形式如下，在标准输入上给出：

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

* * *

### 部分分

部分分根据以下条件设定：

*   对于压缩列中非零元素的数量不超过2000的数据集，正确回答将获得50分。

### 输出

输出压缩列表示的数列的冒泡排序交换次数除以 $10^9+7$ 的余数。

注意，在输出的最后要有换行符。

* * *

### 输入例子1

```plain

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

输出例子1

45

输入例子2

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

输出例子2

509114582