Kavi 在 $$$OX$$$ 轴上有 $$$2n$$$ 点,其中 $$$i$$$ 位于 $$$x = i$$$ 处。
Kavi 考虑了将这些 $$$2n$$$ 点分成 $$$n$$$ 对的所有方法。其中,他对良好的配对感兴趣,其定义如下:
考虑$$$n$$$ 段,其末端位于对应对中的点处。如果对于每个 $$$2$$$ 不同的段 $$$A$$$ 和 $$$B$$$ 其中至少满足以下条件之一,则该配对被称为良好:
- $$$A$$$ 和 $$$B$$$ 段之一完全位于另一个段内。
- $$$A$$$ 和 $$$B$$$ 具有相同的长度。
考虑以下示例:
$$$A$$$ 是一个很好的配对,因为红色部分完全位于蓝色部分内。
$$$B$$$ 是一个很好的配对,因为红色和蓝色部分具有相同的长度。
$$$C$$$ 不是一个好的配对,因为红色或蓝色部分都不位于另一个部分内部,它们的大小也不相同。
卡维对好配对的数量感兴趣,所以他希望你为他找到它。由于结果可能很大,请对 $$$998244353$$$ 求该数。
如果某些两个点在某些配对中属于一对,而在另一个配对中属于不同对,则两个配对被称为不同的。
输入
输入的单行包含单个整数 $$$n$$$ $$$(1\le n \le 10^6)$$$。
输出
打印以 $$$998244353$$$ 为模的良好配对的数量。
示例
输入 #1
1
输出 #1
1
输入 #2
2
输出 #2
3
输入 #3
3
输出 #3
6
输入#4
100
输出#4
688750769
注意
第二个示例的良好配对是:
在第三个示例中,好的配对是: