問題一覧 > 通常問題

No.1681 +-*

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
10 ProblemId : 6806 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-30 21:27:50

問題文

非負整数からなる $N$ 項の数列 $A_1,A_2,\dots ,A_N$ があります。

この数列の隣接する $2$ 項間のそれぞれに $+,-,\times$ の $3$ 種類の演算子のいずれかを入れて数式を作り、計算を行うことを考えます。
なお、計算は通常の規則通り、掛け算を他の演算より優先します。

あり得る数式は $3^{N-1}$ 通りありますが、その全ての数式の計算結果の総和を取った値を求めてください。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください(答えは必ず非負整数になることが証明できます)。

入力

$N$
$A_1\ \ A_2\ \ \cdots\ \ A_N$

  • $2\le N\le 2\times 10^5$
  • $0\le A_i \le 10^9$
  • 入力は全て整数である。

出力

あり得る数式の計算結果の総和を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
1 2 3
出力
16

$1+2-3=0,\ 1+2\times 3=7$ などの $9$ 通りの数式の計算結果の総和を取ると $16$ になります。

サンプル2
入力
5
1001 1002 1003 1004 1005
出力
342428517

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。