公平なコイン（表が出る確率と裏が出る確率がそれぞれ 50% であるコイン）が与えられています。このコインを使って $n$ 個の整数の列 $a_1, a_2, \dots, a_n$ を生成したいと考えています。そのために、以下の手順をちょうど $n$ 回繰り返します。
- 裏が出るまでコインを投げ続けます。
- 止まるまでに表が $k$ 回出たとします。
- 整数 $k$ が生成され、列の末尾に追加されます。
整数の列 $b_1, b_2, \dots, b_m$ に対して、$\text{mex}(b_1, b_2, \dots, b_m)$ を以下の条件を満たす最小の非負整数 $x$ と定義します。
- すべての $1 \le i < x$ に対して、$b_j = i$ となる $1 \le j \le m$ が存在する。
- すべての $1 \le j \le m$ に対して $b_j \neq x$ である。
例えば、$\text{mex}(0, 1, 0, 3) = 2$、$\text{mex}(4, 3, 2, 1, 0, 6, 7, 5) = 8$、$\text{mex}(1, 2, 3) = 0$ です。
今、$\text{mex}(a_1, a_2, \dots, a_n)$ の期待値を $998\,244\,353$ で割った余りを計算したいと考えています。
入力
入力の最初の行には、単一の整数 $n$ ($1 \le n \le 10^5$) が含まれます。
出力
答えを $998\,244\,353$ で割った余りを単一の行に出力してください。
入出力例
入出力例 1
1
499122177
入出力例 2
3
561512450
注記
最初の例において：
- $a_1 = 0$ の場合、$\text{mex}(a_1) = 1$ となります。これが起こる確率は $1/2$ です。
- それ以外の場合、$\text{mex}(a_1) = 0$ となります。
したがって、答えは $1 \times \frac{1}{2} + 0 \times (1 - \frac{1}{2}) = \frac{1}{2} \equiv 499122177 \pmod{998\,244\,353}$ となります。