#6570. 毛毛虫计数

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ghj1222

题目描述

hsezoi 巨佬 olinr 喜欢 van 毛毛虫,他定义毛毛虫是一棵树,满足树上存在一条树链,使得树上所有点到这条树链的距离最多为 1 。给定 n 。现在请你求出 n 个点、有标号的毛毛虫的数量。答案对 998244353 取模。

输入格式

输入只有一行一个整数 n

输出格式

输出一行,表示答案。

样例

样例输入

5

样例输出

125

数据范围与提示

对于 40% 的数据,对于第 i 个测试点有 n=i+4
对于 100% 的数据, n\le10^5