AT_bcu30_f 数列と計算

[problemUrl]: https://atcoder.jp/contests/bcu30/tasks/bcu30_f ある町に、数列が大好きな黒猫と計算が大好きな狼が住んでいます。今日は、二人である数列をもとに計算をして遊ぶことにしました。 黒猫は、長さ $ N $ の整数列 {$ a_i $} を持っていて、この数列の隣り合う項の間に $ + $ または $ \times $ を挿入した式を作り、狼がその値を計算しようとしています。 二人はこの整数列を使いできるだけ長く遊びたいので、作ることができる全ての式 ($ 2^{N-1} $ 通りある) を作り、それらの式の値の合計を求めることにしました。 最終的に答えが合っているかどうかをチェックしたいので、二人はこれらの合計を $ 1,000,000,007\ (=\ 10^9\ +\ 7) $ で割ったあまりを求めるプログラムを作ることを、プログラミングコンテストで日々鍛錬を続けているあなたに頼んできました。 あなたはこの値を計算するプログラムを作ることで、二人を助けてください。 ただし、 $ \times $ は $ + $ よりも計算の優先順序が高いことに注意してください。

入力は以下の形式で与えられる。 > $ N $ $ a_1 $ ... $ a_N $

求める答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ a_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - $ a_i $ $ (1\ \leq\ i\ \leq\ N) $ は整数である。 ### Sample Explanation 1 考えられる数式は、 $ 1+2+3 $ と $ 1+2\ \times\ 3 $ と $ 1\ \times\ 2+3 $ と $ 1\ \times\ 2\ \times\ 3 $ の $ 4 $ 種類です。 これらの式を計算すると、それぞれ答えは $ 6 $、$ 7 $、$ 5 $、$ 6 $ となるので、合計は $ 6+7+5+6=24 $ です。 ### Sample Explanation 2 求める合計は $ 1000000007\ (=\ 10^9+7) $ となるので、これを $ 10^9+7 $ で割ったあまりである $ 0 $ を出力します。