Problem Statement

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

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

長さ $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

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

Constraints

• $N > 0$
• $-10^5 ≦ A_i ≦ 10^5(1 ≦ i ≦ N)$
• $A_i ≠ 0$ なる $i$ の個数は $10^5$ を超えない。
• 与えられる圧縮列からは、上述の方法によって元の数列が復元できることが保障される。
• 入力はすべて整数である。

Input

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

N
A_1 ... A_N

部分点

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

• 圧縮列の $0$ でない要素の個数が $2000$ を超えないデータセットに正解した場合、部分点として$50$点が与えられる。

Output

圧縮列が表す数列のバブルソートの交換回数を $10^9+7$ で割った余りを出力せよ。

出力の最後には改行を忘れないこと。