A85991.毛毛虫计数

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:512MB

题目描述

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

输入格式

输入只有一行一个整数 nn

输出格式

输出一行,表示答案。

输入输出样例

  • 输入#1

    5

    输出#1

    125

说明/提示

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

首页