問題一覧 > 通常問題

No.1334 Multiply or Add

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 36
作問者 : penguinman / テスター : 夕叢霧香(ゆうむらきりか)
お気に入りにしたユーザー ProblemId : 5459 / 自分の提出
問題文最終更新日: 2021-01-17 04:29:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 277 (順位表) の他の問題:

Problem Statement

Consider an expression with $N$ terms, $A_1\ op_1\ A_2,\ldots,op_{N-1}\ A_N$. Each $A_i$ is a positive integer, and each $op_i$ is one of the symbols '+' or '×'.

Given $N$ and $A_1,\ A_2,\ldots,A_N$, assign symbols to the $op_i$ appropriately so as to maximize the result of the expression, and output the maximum value.

Since this value can be very large, output it modulo $10^9+7$.

As in ordinary expressions, multiplication takes precedence over addition.

Input

$N$
$A_1\ A_2\ldots A_N$
  • $2≤N≤2×10^5$
  • $1≤A_i≤10^9$
  • All inputs are integers

Output

Output the maximum value of the result, modulo $10^9+7$.

Sample

Sample 1
Input
4
2 1 3 1
Output
7

$2×1×3+1$ and $2+1+3+1$ attain the maximum value.

Sample 2
Input
5
5 1 4 2 3
Output
120

$5×1×4×2×3$ attains the maximum value.

Sample 3
Input
7
11032 193029 8284 13828 73476 1391 10
Output
518962052

Find the remainder modulo $10^9+7$.

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