#P51942. 「LOJ」 毛毛虫计数

「LOJ」 毛毛虫计数

题目描述

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

输入格式

输入只有一行一个整数 nn

输出格式

输出一行,表示答案。

样例

5
125

数据范围与提示

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