Friend of Friend is Friend

問題文

以下のように説明されるものを、 $n$ 人のユーザーからなるSNSとします。

• SNSには $n$ 人のユーザーがおり、 $i ~ (1 \leq i \leq n)$ 人目のユーザーをユーザー $i$ という。

• SNSには、 $2$ 人のユーザが互いに友達になれる機能がある。
  友達関係は双方向的である。すなわち、ユーザー $x$ とユーザー $y$ が友達ならば、必ずユーザー $y$ とユーザー $x$ は友達である。

また、「ユーザー $x$ とユーザー $y$ が友達かつユーザー $y$ とユーザー $z$ が友達ならば、必ずユーザー $x$ とユーザー $z$ は友達である」ことを必ず満たすとき（またそのときに限り）このSNSは楽しいSNSであるとします。

正整数 $N$ が与えられます。$N$ 人のユーザーからなる楽しいSNSとしてあり得るものの個数を $998244353$ で割った余りを求めてください。

ここで $2$ つのSNSは、ある $x, y$ が存在し、一方ではユーザー $x$ とユーザー $y$ が友達であり、他方では友達ではないものがあるとき区別します。

制約

• $N$ は整数
• $2 \leq N \leq 3 \times 10^5$

入力

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

出力

答えを出力せよ。

サンプル 1

3

5

サンプル 2

300000

111180233