完全图染色（困难版）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个有 $n$ 个有标号顶点的无向完全图。你需要把每条边染成红色或蓝色。

若顶点集 $S$ 的红色诱导子图连通，则称 $S$ 红连通；蓝连通同理。要求：

• 至少有一条红边和一条蓝边；
• 对每个 $|S|\ge2$ 的顶点集 $S$，红色诱导子图与蓝色诱导子图中恰有一个连通。

求不同染色方案数，对 $998244353$ 取模。

输入格式

输入一个整数 $n$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入 1

3

样例输出 1

6

样例输入 2

4

样例输出 2

50

数据范围

$3\le n\le5\cdot10^4$。

说明

顶点有标号，交换两个顶点通常会得到不同的染色方案。