Story

You do not necessarily need to read this section.

Consider the situation of dividing people into teams for some competition.

Let the strength of a team simply be the total strength of the people belonging to that team. Then, for the same number of teams, the larger the product of the strengths of all teams, the less unbalanced the division can be considered to be.

Let us consider performing such a calculation for all possible team divisions.

Problem Statement

You are given a sequence $A$ of length $N$. A set $S$ of sets of positive integers is called a "good grouping" if it satisfies all of the following.

• For any element $T$ of $S$, $\lvert T \rvert \geq 1$
• $\displaystyle\sum_{T \in S} \lvert T \rvert = N$
• For any distinct elements $T,U$ of $S$, $T \cap U=\varnothing$
• For every integer $i$ between $1$ and $N$, inclusive, there exists some $T \in S$ such that $i \in T$

For every good grouping $S$, compute the following value, and find the sum of these values. Since the answer can be very large, output it modulo $998244353$.

• $\displaystyle\prod_{T \in S} \displaystyle\sum_{i \in T} A_{i}$

Constraints

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq A_{i} \leq 10^{18}$
• All inputs are integers.

Input

$N$
$A_{1}~~~A_{2} ~~\ldots ~~A_{N}$

Output

Output the answer.

Sample

3
1 2 3

34

1
1

1

5
1 1 1 1 1

196