图染色（简单版）

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

题目描述

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

对于顶点集合 $S$，若 $S$ 中任意两点之间都存在一条只经过 $S$ 中顶点、且全部由红边组成的路径，则称 $S$ 红连通。蓝连通的定义类似。

请计算满足以下条件的染色方案数：

• 至少有一条红边；
• 至少有一条蓝边；
• 对每个满足 $|S|\ge2$ 的顶点集合 $S$，红连通与蓝连通恰好有一个成立。

答案对 $998244353$ 取模。

输入格式

输入一行一个整数 $n$。

输出格式

输出一个整数，表示合法染色方案数模 $998244353$ 的结果。

样例输入 1

3

样例输出 1

6

样例输入 2

4

样例输出 2

50

样例输入 3

100

样例输出 3

878752271

数据范围

$3\le n\le5000$。

各子任务数据彼此独立计分。