2392. [HZOI 2015]有标号的二分图计数 I

【题目描述】

$QAQ$ 喜欢玩二分图

他随机生成了很多很多有 $n$ 个点的简单二分图,然后他对这些图进行黑白染色

他认为这些染色后的图看上去非常的赏心悦目

于是他决定把所有这样赏心悦目的图作为礼物送给妹子

不过在这之前,$QAQ$ 想知道有多少种不同的赏心悦目的图

注意,两个图不同至少要满足以下两个条件之一:

$1$、一个图中存在边 $(u,v)$ 而另一个图中不存在

$2$、存在点 $u$ 在两个图中的颜色不同

【输入格式】

输入一个 $n$ 表示点数

【输出格式】

输出一个数表示赏心悦目的图的方案数

由于输出可能很大,$QAQ$ 只想知道输出对 $998244353$ 取模后的结果

【样例输入】

2

【样例输出】

6

【样例解释】

有以下 $6$ 种方案

$1$、$(1,2)$ 为白色,无边

$2$、$(1,2)$ 为黑色,无边

$3$、$(1)$ 为黑色，$(2)$ 为白色，无边

$4$、$(1)$ 为白色，$(2)$ 为黑色，无边

$5$、$(1)$ 为黑色，$(2)$ 为白色，有 $(1,2)$ 边

$6$、$(1)$ 为白色，$(2)$ 为黑色，有 $(1,2)$ 边

【数据规模】

对于 $30\%$ 的数据，有 $n \leq 5000$

对于 $100\%$ 的数据，有 $n \leq 100000$