Exchange of gifts

2 secs 1024 MB
akinyan

問題文


~の番号のついた人の人と個のプレゼントあります。今、人がプレゼントを持っています。
この人でプレゼントの交換をします。人がプレゼントをもらうことが少なくとも1回あるのは何通りですか?
答えはとても大きくなる可能性があるので 998244353 で割った余りを出力してください。

制約


  • は整数

入力


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

N

出力


答えを 998244353 で割った余りで出力してください。

サンプル


入力1
3
出力1
4

人1がプレゼント1、人2がプレゼント2、人3がプレゼント3をもらうとき
人1がプレゼント1、人2がプレゼント3、人3がプレゼント2をもらうとき
人1がプレゼント2、人2がプレゼント1、人3がプレゼント3をもらうとき
人1がプレゼント3、人2がプレゼント2、人3がプレゼント1をもらうとき
の4通りが満たします。

入力2
100
出力2
812338988

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

提出


Go (1.14)