题目描述

给一个长度为 $n$ 的序列 $\{a_i\}$，一开始你有一个数 $A = 0$，每次可以从序列中选一个数 $b$，令 $A = A + b$ 或者 $A = A \times b$，每个数都要使用一次，加的次数要和乘的次数近可能相近，要求最大化 $A$，输出 $A$ 对 $998244353$ 取模的值。

输入格式

第一行为一个整数 $n$，表示序列的长度。

第二行为 $n$ 个整数 $a_i$，描述这个序列，其中 $2 \leq n \leq 10^3$，$1 \leq a_i \leq 10^9$。

输出格式

一个非负整数，表示 $A$ 的最大值对 $998244353$ 取模的值

输入输出样例

4
3 3 2 4

60

说明/提示

$(2+3)×3×4=60$