在充满活力的罗马尼亚，FS 正在为他的传奇演唱会做准备。他的标志性歌曲《Sfântul Trapez》即将震撼舞台，每一位粉丝都在热切地等待着这场演出。但 FS 为这次表演准备了一个特别的转折：他计划了一个独特的游戏来娱乐观众。

在这个音乐游戏中，FS 构想了一个宏大的魔法图来代表他的演唱会，其中每个顶点都是一名表演者，每条边都是他们之间生动的连接。在压轴戏中，FS 决定探索这些连接的秘密。他想知道他的图中存在多少条“关键边”。他定义一条边为关键边，当且仅当移除该边会增加图的连通分量数量。

为了增加趣味性，FS 设想了所有可能的表演者图配置，并提出了一个挑战：计算每种可能的图配置中这些关键边的数量。然后，他计划将所有这些关键边的数量相加，得出总和。

凭借他充满力量的嗓音和戏剧天赋，FS 准备在演唱会上表演并解决这个图论难题。随着人群的欢呼，FS 的标志性节拍与他图论游戏的复杂性结合在一起，形成了一场音乐与数学奇迹的难忘盛宴。

因此，挑战很明确：计算所有具有 $n$ 个顶点的带标号图的关键边总数，让演唱会的能量点亮数学！你需要通过计算该结果对 $998\,244\,353$ 取模后的值来模拟这场演出的成功。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)。

输出格式

输出一个整数：所求的总和对 $998\,244\,353$ 取模的结果。

样例

输入 1

3

输出 1

9

输入 2

8

输出 2

130981312