問題文

高橋君は、毎年誕生日にお母さんから数列をもらっています。 高橋君はバブルソートの交換回数を求めるのが好きなので、毎年、お母さんからもらった数列のバブルソートの交換回数を求めるのを楽しんできました。

しかし今年のお母さんは一味違います。なんと、高橋君がバブルソートの交換回数を求めるのをより一層楽しめるように、とても長い数列を圧縮したものを高橋君に渡したのです。

長さ $10^7$ の数列のバブルソートの交換回数なら目視で $1$ 秒とかからずに求められる高橋君でも、この数列には歯が立ちませんでした。

あなたの仕事は、高橋君に代わってこの数列のバブルソートの交換回数を $10^9+7$ で割ったあまり求めることです。

ただし、バブルソートとは、以下の擬似コードで与えられるアルゴリズムです。

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\])
      }
}

バブルソートの交換回数とは、上の疑似コードでswapが呼ばれる回数です。

また、圧縮された列からもとの数列を得る方法は、以下の通りです。

• 最初、ポインタは圧縮列の最初の項を指しており、スタックは空である。以下の操作をポインタの位置が圧縮列からはみ出すまで繰り返す。最終的にスタックに残ったひとつの数列が、目的の数列である。
• ポインタの指す値が正なら、スタックにその値の項ひとつからなる数列を積み、ポインタを一つ進める。
• ポインタの指す値が $0$ なら、スタックの上から $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)$
*   $A_i ≠ 0$ なる $i$ の個数は $10^5$ を超えない。
*   与えられる圧縮列からは、上述の方法によって元の数列が復元できることが保障される。
*   入力はすべて整数である。

### 入力

入力は以下の形式で標準入力から与えられる。

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

* * *

### 部分点

この問題には部分点が設定されている。

*   圧縮列の $0$ でない要素の個数が $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