Migrated from Lutece 2877 简单算术

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个正整数 $n$ 和 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，求

$$\left[\prod_{1 \leq i, j \leq n} (a_i+a_j)\right] \bmod 998244353 $$

Input

第一行包含一个正整数 $n\ (1 \leq n \leq 10^5)$。

第二行包含 $n$ 个以空格分隔的正整数 $a_1,\ldots,a_n\ (1 \leq a_i \leq 998244352)$。

Output

输出所求的值。

Samples

6
1 1 4 5 1 4

39573188

Resources

The 20th UESTC Programming Contest Preliminary