問題文

(1,2,\ldots,N) を並び替えて得られる数列 P のうち以下の条件を満たすものの個数を求め、998244353 で割ったあまりを出力してください。

• すべての i\ (2 \leq i \leq N) について、以下のいずれかが成り立つ。
  • すべての j\ (1 \leq j \lt i) について、P_j \lt P_i
  • すべての j\ (1 \leq j \lt i) について、P_j \gt P_i

制約

• 2 \leq N \leq 10^{18}
• N は整数

入力例 1

2

出力例 1

2

(1,2) を並び替えて得られる数列は (1,2) と (2,1) の 2 つですが、そのどちらもが問題文中の条件を満たします。

入力例 2

659636104093210683

出力例 2

512716103

998244353 で割ったあまりを出力してください。

原案: penguinman