← 返回题目列表

Codeforces · 1792/F2

F2. 图形着色(硬版)

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

简单版本和困难版本之间的唯一区别是对 $$$n$$$ 的约束。

给你一个 $$$n$$$ 个顶点的无向完整图。完全图是每对顶点都由边连接的图。您必须将图表的边缘绘制为两种颜色:红色和蓝色(每个边缘都有一种颜色)。

一组顶点 $$$S$$$ 是红色连接的,如果对于每对顶点 $$$(v_1, v_2)$$$ 使得 $$$v_1 \in S$$$ 和 $$$v_2 \in S$$$ 存在一条从 $$$v_1$$$ 到 $$$v_2$$$ 的路径,该路径仅通过红色边并且来自 $$$S$$$ 的顶点。类似地,如果对于每对顶点 $$$(v_1, v_2)$$$ 使得 $$$v_1 \in S$$$ 和 $$$v_2 \in S$$$ 存在一条从 $$$v_1$$$ 到 $$$v_2$$$ 的路径,该路径仅通过蓝色边,并且顶点来自$$$S$$$。

您必须以以下方式绘制图表:

- 至少有一个红色边缘;
- 至少有一个蓝色边缘;
- 对于每组顶点 $$$S$$$ 使得 $$$|S| \ge 2$$$, $$$S$$$ 要么是红色连接的,要么是蓝色连接的,但不能同时连接。

计算绘制图形的方法数量,并以 $$$998244353$$$ 为模进行打印。

输入

第一行(也是唯一的一行)包含一个整数 $$$n$$$ ($$$3 \le n \le 5 \cdot 10^4$$$)。

输出

打印一个整数 — 绘制图形的方式数,以 $$$998244353$$$ 为模。

示例

输入 #1

3

输出 #1

6

输入 #2

4

输出 #2

50

输入 #3

100

输出 #3

878752271

输入#4

1337

输出#4

520628749

输入 #5

42013

输出 #5

906821221