[SXZOI 2024 C] 典

题目背景

现在我说，这真的是典。

你信吗？

是吗？是吧。

题目描述

给定一个整数 $n$。

你有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，值域为 $[1,n]$。

从 $n^n$ 个可能的序列 $a$ 中，等概率地随机选出一个。接下来建出一张有向图，对于每个 $i$，$i\to a_i$ 有一条有向边连接。

我们从 $n$ 个点里等概率地随机选出一个点，求出这个点能到达的点数的期望值。

答案对 $998244353$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行一个非负整数，表示答案。

样例 #1

样例输入 #1

2

样例输出 #1

499122178

样例 #2

样例输入 #2

288

样例输出 #2

20712964

提示

对于所有数据，保证 $1 \leq n \leq 10^6$。

对于前 $20%$ 的数据，保证 $1 \leq n \leq 5$。

对于前 $60%$ 的数据，保证 $1 \leq n \leq 2000$。