← 返回题目列表

Codeforces · 1528/B

B. 卡维配对值班

中文机器翻译题面 查看原题

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

注意

第二个示例的良好配对是:

在第三个示例中,好的配对是: