题目描述

瓜瓜在玩飞行棋的时候，想到了一个问题：期望扔多少次骰子可以到达终点？

具体的说，每一次行动之前先投掷一个 $6$ 面的骰子，随机生成一个 $1$ 到 $6$ 的整数，以此决定向终点移动的步数。

特别的，如果扔出的数字大于离终点的距离，多余的步数会回退。例如在 $2$ 的位置扔出了数字 $6$ ，则会移动到 $2 \to 1 \to 0 \to 1 \to 2 \to 3 \to 4$ 。下次移动仍是朝着终点的。

只有恰好移动到终点，游戏才结束，否则要一直扔。

瓜瓜告诉你他现在在位置 $n$ ，想要去往终点 $0$ ，希望你能告诉他，期望扔多少次骰子可以到达终点？

输入格式

一个正整数 $n(n \leqslant 10^4)$ ，表示瓜瓜离终点的距离。

一个数字，表示期望次数，对 $998244353$ 取模。

有理数取模：如果答案是 $\frac{P}{Q}$ 的形式，若存在 $R$ 满足 $QR \equiv 1 \pmod {998244353}$ ，那么取模后的答案是 $PR \bmod 998244353$ 。

891949823