Alice 和 Bob 正在玩一个游戏。 他们给定一个排列 $p$，并轮流执行以下操作，Alice 先手：
- 操作：将 $p_1 \dots p_n$ 重新排列成任意顺序。
如果某人执行了两次相同的 $p_1$，则该人输掉比赛。 Alice 和 Bob 都非常聪明，总是会选择最优操作来确保获胜。 给定所有大小为 $n$ 的排列，确定其中有多少个排列 Bob 会获胜，结果对 $998244353$ 取模。
输入格式
输入的第一行包含一个整数 $n$ ($1 \le n \le 10^7$)。
输出格式
输出一行，包含一个整数，表示答案。
样例
样例输入 1
1
样例输出 1
1
样例输入 2
2
样例输出 2
1
样例输入 3
10
样例输出 3
997920
样例输入 4
100
样例输出 4
188898954