問題文

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

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

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

部分点

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

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

出力

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

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

入力例1

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