Pyramid of Differences

(writerが過去にXで公開した問題です。)

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます。 あなたはこの整数列に対して、以下の操作を $N-1$ 回行います。

• 現在の $A$ の長さを $k$ とする。長さ $k-1$ の整数列 $X=(X_1,X_2,\cdots,X_{k-1})$ であって、各 $1\le i\le k-1$ に対して $|X_i|=|A_{i+1}-A_i|$ を満たすようなものを一つ定める。そして、$A$ を $X$ で置き換える。

$N-1$ 回操作を行った後 $A$ の長さは $1$ になりますが、このときの $A_1$ が取りうる最大値を $998244353$ で割ったあまりを求めて下さい。

制約

• $2\le N\le 2\times 10^5$
• $-10^9\le A_i\le 10^9\ (1\le i\le N)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

サンプル 1

入力

3
3 1 4

出力

5

例えば、操作によって $A$ を $(3,1,4)\rightarrow (-2,3)\rightarrow (5)$ と変化させることができます。

サンプル 2

入力

8
16 -5 -16 3 -3 0 -7 3

出力

589