F. Subset Mex - 水以下コンテスト

F - Subset Mex

Ceylon

1024

100

点

$N$ 枚のカードが一列に並べられており、左から $i$ 番目のカードには非負整数 $A_i$ が書かれています。

$N$ 枚のカードから $1$ 枚以上選ぶ方法は $2^N - 1$ 通りありますが、そのすべてについて以下の値を求め、
総和を $998244353$ で割った余りを求めてください。

左から $B_1, B_2, \ldots, B_K$ 番目のカードを選んだとする。 $\mathrm{mex}(A_{B_1}, A_{B_2}, \ldots, A_{B_K})$ を求める値とする。

ここで、ある数列 $X$ に対して、 $\mathrm{mex}(X)$ は以下の条件を満たす唯一の非負整数 $m$ として定義します。

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

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

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

$1$ 行で、カードを $1$ 枚以上選ぶようなすべての選び方について、求める値を足し合わせた値を $998244353$ で割った余りを出力せよ。

入力例 1

4
0 1 1 2

出力例 1

カードを $1$ 枚以上選ぶ選び方と、その時の求める値は以下のようになります。

よって、答えはこれらをすべて足し合わせた $17$ が答えとなります。

このサンプルは部分点1の制約を満たします。

入力例 2

12
2 0 2 4 0 3 3 0 1 4 0 0

出力例 2

このサンプルは部分点1の制約を満たします。

入力例 3

25
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3

出力例 3

どのようにカードを選んでも、求める値は $0$ となります。

このサンプルは部分点2の制約を満たします。