You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice 和 Bob 在一张 $n$ 个点的无向图上博弈，Alice 和 Bob 轮流操作，Alice作为先手。

具体的，每次轮到一个人操作，如果 $1$ 号点和 $n$ 号点是联通的，那么这个人赢下比赛，否则他需要选择两个节点 $u,v$ ，保证这两个点之间当前没有边，然后在这两个点之间建一条边。

Alice 和 Bob 足够聪明，他们会按照最优策略操作。

Alice想知道有多少个大小为 $n$ 的完全图的生成子图，能够使他赢下比赛。

完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

生成子图是由一个图的全部顶点及连结这些顶点的部分边构成的图。两个生成子图 $G_1,G_2$ 不同当且仅当有一条边在 $G_1$ 中出现但在 $G_2$ 中不出现，亦或相反。

$n$ 个点的完全图有 $\frac{n(n-1)}{2}$ 条边， $2^{\frac{n(n-1)}{2}}$ 个不同的生成子图。

输入格式

输入一行一个整数 $n$ 表示完全图的大小。

输出格式

输出一行一个整数，表示能让 Alice 获胜的生成子图数量，结果可能较大，你只需要输出答案在模 $998244353$ 意义下的结果。

样例 #1

样例输入 #1

3

样例输出 #1

6

样例 #2

样例输入 #2

5

样例输出 #2

952

样例 #3

样例输入 #3

99

样例输出 #3

851406784

提示

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于 $75\%$ 的数据（前 $15$ 个测试点），满足对于第 $i$ 个测试点， $n=i+1$ ，也就是说前 $15$ 个测试点的 $n$ 分别为 $2,3,...,16$ 。

对于另外 $10\%$ 的数据，$n \le 50$ 。

对于全部数据，$2 \le n \le 2000$ 。