有标号的二分图计数 III

【题目描述】

[前置技能]：[有标号的二分图计数 $I$] [有标号的二分图计数 $II$]

$QAQ$ 总算完成了去重工作，可是妹子又不满意了

她觉得这些图中有很多图乱七八糟，根本不联通，非常的难看

所以她决定把不联通的图扔掉

可是妹子很懒，于是她就把这个任务交给了 $QAQ$

$QAQ$ 也很懒，所以他想请你告诉他扔掉那些不联通的图之后，他所送的礼物还有多少个图

【输入格式】

输入一个数 $n$ 表示节点数

【输出格式】

输出题目所求方案

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

【样例输入】

2

【样例输出】

1

【样例解释】

只有一种方案

即有边 $(1,2)$

【数据规模】

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

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