問題文

$3$ 人で ’ジャンケン’ をして勝者をきめることにする。 たとえば，$1$ 人が ’紙’ を出し，他の $2$ 人が ’石’ を出せば，ただ $1$ 回でちょうど $1$ 人の勝者がきまることになる。 $3$ 人で ’ジャンケン’ をして，負けた人は次の回に参加しないことにして，ちょうど $1$ 人の勝者がきまるまで，’ジャンケン’ をくり返すことにする。 このとき，$k$ 回目に，はじめてちょうど $1$ 人の勝者がきまる確率 $\pmod{998244353}$ を求めよ。

注記

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

制約

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

入力

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

k

出力

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

サンプル

1

332748118

$1$ 回でちょうど $1$ 人の勝者がきまるのは，

• $1$ 人が ’石’ を出し，残りの $2$ 人が ’ハサミ’ を出す
• $1$ 人が ’ハサミ’ を出し，残りの $2$ 人が ’紙’ を出す
• $1$ 人が ’紙’ を出し，残りの $2$ 人が ’石’ を出す

ときです。このようになる確率は $\frac{1}{3}$ です。

114514

200889667