动感节奏，方块错叠。

Description

小玖有 $n^3$ 个棱长为 $1$ 的小立方体，她决定用其摆成一个 $n\times n\times n$ 的大立方体。

她想给每个小立方体定一个权值。她意识到自己还有一个长度为 $n$ 的序列 $a$，于是她决定给位于从左往右第 $i$ 个，从前往后数第 $j$ 个，从下往上数第 $k$ 个的小立方体的权值定为 $a_i\times a_j\times a_k$。

她觉得，知道一个小立方体的权值是很容易的，所以她想知道所有小立方体的权值的和。

答案可能很大，请对 $998244353$ 取模。

Format

Input

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$，用空格隔开。

Output

一行一个正整数，即答案。

Samples

5
1 1 1 1 1

10

Limitation

对于 $20\%$ 的数据，$1\le n,a_i\le 10$。

对于 $60\%$ 的数据，$1\le n\le 10^3,1\le a_i\le 10^6$。

对于 $100\%$ 的数据，$1\le n\le 10^6,1\le a_i\le 10^9$。