添字が $1$ から始まり、長さが有限の数列を引数とする関数 $f$ を以下のように定義する。
$\displaystyle f(\{a_1, a_2, \ldots, a_n\}) = \sum_{i=1}^n {a_i}^i$
長さ $N$ の数列 $X = \{ x_1, x_2, \ldots, x_N \}$ が与えられるので、空の列を除く全ての部分列 $X'$ に対して $f(X')$ を求め、その総和を $998244353$ で割ったあまりを出力せよ。ただし、部分列の添字は、元の数列における相対的な序列を保ったまま $1$ から順に番号を振り直すものとする。また、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとする。
入力は以下の形式で与えられる。
$N$ $x_1$ $\ldots$ $x_N$
1行目に長さ $N$ が与えられる。 2行目に数列 $X$ の要素が空白区切りで与えられる。
入力は以下の条件を満たす。
空の列を除く全ての部分列 $X'$ について $f(X')$ を求め、その総和を $998244353$ で割ったあまりを出力せよ。
3 1 2 3
64
$(1^1)+(2^1)+(1^1+2^2)+(3^1)+(1^1+3^2)+(2^1+3^2)+(1^1+2^2+3^3) = 64$
であるから、64を出力する。
5 100 200 300 400 500
935740429