一场马拉松比赛将在一个池塘边举行。池塘是圆形的，沿其周长等间距地标记着 $1, 2, \dots, 2N$。比赛共有 $2N$ 名参赛者；其中 $N$ 人戴红帽子，另外 $N$ 人戴白帽子。

马拉松比赛流程如下：

• 对于 $2N$ 个标记点中的每一个，恰好有一名参赛者占据该位置。
• 位于标记为 $1$ 的位置的参赛者接过接力棒，开始顺时针奔跑。
• 第 $i$ 位（$1 \le i \le 2N - 1$）跑步者持续奔跑，直到到达第一个戴着与自己帽子颜色不同的帽子的人的位置。到达该位置后，他/她将接力棒传给那个人并离开池塘。接到接力棒的人开始顺时针奔跑。
• 第 $2N$ 位跑步者通过跑向标记为 $1$ 的位置完成马拉松。

如果绕池塘一圈的长度为 $1$，则 $2N$ 名参赛者所跑距离之和为一个整数，记为 $L$。

共有 $(2N)!$ 种可能的参赛者排列方式。求所有排列方式的 $L$ 之和，对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$

• 所有输入数字均为整数。
• $1 \le N \le 10^6$

输出格式

在一行中输出答案。

样例

样例输入 1

1

样例输出 1

2

样例输入 2

2

样例输出 2

40

样例输入 3

3

样例输出 3

1656

样例输入 4

4

样例输出 4

112896

样例输入 5

5

样例输出 5

11750400

说明

对于第一个样例，共有 $2$ 种可能的排列，且两种情况下 $L = 1$。

对于第二个样例，如果占据标记为 $1, 2, 3, 4$ 位置的参赛者所戴帽子颜色分别为：

• 红、红、白、白，则 $L = 2$。
• 红、白、红、白，则 $L = 1$。
• 红、白、白、红，则 $L = 2$。
• 白、红、红、白，则 $L = 2$。
• 白、红、白、红，则 $L = 1$。
• 白、白、红、红，则 $L = 2$。

每种颜色排列对应 $4$ 种可能的参赛者排列。所有 $24$ 种排列的 $L$ 之和为 $(2 + 1 + 2 + 2 + 1 + 2) \times 4 = 40$。