背景

あおばさんは 2 つのコンテストでの順位の積の値を競う大会に参加し、現在 1 つ目のコンテストが終了しました。
あおばさんは単独優勝できるでしょうか?

問題文

正の整数 N が与えられます。 n=1,2,\dots,N について以下の問題を解いてください。

(1,2,\dots, N) の順列 P=(P_1,P_2,\dots,P_N) であって、m=1,2,\dots,N 全てについて

\[n\neq m\implies nP_n<mP_m\]

が成り立つものの個数を 998244353 で割った余りを求めよ。

制約

• 1 \leq N \leq 5\times 10^5
• 入力は全て整数

部分点

• 追加の制約 N\le1000 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

3

出力例 1

3
1
0

• n=1 のとき条件を満たす順列は P=(1,2,3),(1,3,2),(2,3,1) の 3 つです。
• n=2 のとき条件を満たす順列は P=(3,1,2) の 1 つです。
• n=3 のとき条件を満たす順列は存在しません。