简单版本和困难版本之间的唯一区别是对 $$$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