問題文

どの目も出る確率が $\dfrac{1}{6}$ のさいころを $1$ つ用意し，次のように左から順に文字を書く。

さいころを投げ，出た目が $1, 2, 3$ のときは文字列 $\mathrm{AA}$ を書き，$4$ のときは文字 $\mathrm{B}$ を，$5$ のときは文字 $\mathrm{C}$ を，$6$ のときは文字 $\mathrm{D}$ を書く。 さらに繰り返しさいころを投げ，同じ規則に従って，$\mathrm{AA, B, C, D}$ をすでにある文字列の右側につなげて書いていく。

たとえば，さいころを $5$ 回投げ，その出た目が順に $2, 5, 6, 3, 4$ であったとすると，得られる文字列は，

となる。このとき，左から $4$ 番目の文字は $\mathrm{D}$，$5$ 番目の文字は $\mathrm{A}$ である。

$n$ を正の整数とする。$n$ 回さいころを投げ，文字列を作るとき，文字列の左から $n$ 番目の文字が $\mathrm{A}$ となる確率 $\pmod{998244353}$ を求めよ。

注記

求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では，その値を互いに素な $2$ つの整数 $P, Q$ を用いて $\frac{P}{Q}$ と表したとき，$R \times Q \equiv P \pmod{998244353}$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $1 \leq n \leq 2 \times 10^5$

入力

入力はすべて整数である。

n

出力

計算結果を一行に出力せよ。

サンプル

1

499122177

$1$ 回さいころを投げたとき，左から $1$ 番目の文字が $\mathrm{A}$ となるのは $1, 2, 3$ のいずれかの目が出たときです。 このようになる確率は $\frac{1}{2}$ です。

114514

849351066