你正在开发一套名为 Biological Software Utilities (BSU) 的软件工具包。该工具包包含一个专门用于树识别的程序。回想一下，树是一个无环的连通无向图。

在自然界中，树生长时会同时增加两个相邻的顶点。因此，你认为一棵树是“合理的”（plausible），当且仅当在移除某些边后，所得的图仅由包含 2 个顶点的连通分量组成。换句话说，一棵树是合理的，当且仅当它存在完美匹配。

现在你需要为 BSU 实现一个新功能，用于计算具有 $n$ 个顶点的合理树的数量，其中顶点编号为 $1$ 到 $n$ 的不同整数。如果存在一条边 $(u, v)$ 仅存在于其中一棵树中，则认为这两棵树不同。

由于合理树的数量可能非常大，你需要计算其对 $998\,244\,353$ 取模的结果。

输入格式

仅一行，包含一个整数 $n$，表示树的顶点数 ($1 \le n \le 10^6$)。

输出格式

输出具有 $n$ 个顶点的合理树的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

1

样例输出 1

0

样例输入 2

2

样例输出 2

1

样例输入 3

3

样例输出 3

0

样例输入 4

4

样例输出 4

12

样例输入 5

7788

样例输出 5

178152092