Sum functions Sum

長さ の整数列 が与えられます。
整数 と非負整数 に対して関数 は以下のように定義されます。

このとき、 の値を求めて下さい。 ただし、答えは非常に大きくなる場合があるので、 で割った余りを求めて下さい。

• 入力される値は全て整数である。

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

答えを一行に出力して、最後に改行せよ。

2 1 1 1 -1
1 2

3

です。

2 5 1 1 -1
1 2

30

5 5 1 1 -2
3 1 4 1 5

170

7 314 15 9 -2
6 5 3 5 8 9 7

45643497