$n$ people are arranged in a circle, labeled $1, 2, \dots, n$ in order, and each person has a pot.

Each person $i$ can choose to pass their pot to any of the other $n-1$ people, or choose not to pass the pot. According to the First Law of Pot-Passing, the passing behavior cannot form a cycle. That is, there cannot exist a sequence $v_1, v_2, \dots, v_k, v_{k+1}$ such that $v_{k+1} = v_1$, where for each $1 \le i \le k$, person $v_i$ passes their pot to person $v_{i+1}$. Since such a scenario would always result in at least one pot that cannot be resolved, such a passing scheme is clearly illegal.

We use "Gu-value" to quantify the impact of pot-passing behavior on task completion efficiency. Research shows that the Gu-value of a single pot-passing action depends only on the relative position of the passer and the receiver on the circle. Specifically, if person $i$ decides to pass the pot to person $j$, their Gu-value is $\omega_{(i-j+n)\bmod n}$, where $\omega_k$ is a given parameter. If person $i$ decides not to pass the pot, their Gu-value is $1$.

We define the Gu-value of a legal pot-passing scheme as the product of everyone's Gu-values. Calculate the sum of the Gu-values of all possible legal pot-passing schemes, modulo $998\,244\,353$. Two pot-passing schemes are considered different if and only if there exists at least one person whose choice is different (i.e., whether they chose to pass the pot, and if so, to whom).

Input

The input is read from standard input.

The input consists of two lines. The first line contains a positive integer $m$, where $n=2^m$ as described in the problem.

The next line contains $n-1$ space-separated integers $\omega_1, \omega_2, \dots, \omega_{n-1}$, where $\omega_i \in [0, 998\,244\,353)$.

Output

Output to standard output.

Output a single integer representing the sum of the Gu-values of all possible schemes, modulo $998\,244\,353$.

Examples

Input 1

3
1 2 3 4 5 6 7

Output 1

148656674

Constraints

For $20\%$ of the data, $m \le 3$;

For $40\%$ of the data, $m \le 8$;

For $60\%$ of the data, $m \le 12$;

For another $20\%$ of the data, all $\omega_k$ are equal;

For $100\%$ of the data, $2 \le m \le 20$, $\omega_k \in [0, 998\,244\,353)$.