稻妻的统治者雷电将军正在玩她朋友八重神子发明的一种新卡牌游戏。
Pixiv ID: 93716380
玩家需要通过合理使用魔法卡来击败生命值（HP）为 $n$ 的怪物。具体来说，有三种魔法卡：
- 水人（Waterman）：召唤水人到场上，水人将永久留在场上。每当你施放一张魔法卡且水人已经在场上时，它会使怪物的 HP 减少 1。注意，如果你在水人已经在场时施放另一张水人卡，除了怪物 HP 减少 1 外，不会发生其他任何事情。
- 火球（Fireball）：使怪物的 HP 减少 2。
- 复制（Copy）：复制在此卡之前施放的任意一张卡，并获得该被复制卡的一张拷贝。
在每一回合开始时，玩家以 $\frac{1}{3}$ 的等概率获得三种卡牌中的一种。然后，玩家可以选择依次施放手中的一些魔法卡，施放的卡牌将分别产生效果。由于手牌数量没有限制，玩家可以选择保留卡牌，在本回合什么都不做。
如果怪物的 HP 变为非正数，则怪物被击败。现在雷电将军希望你计算出，如果她采取最优策略以最小化期望回合数，击败怪物所需的期望回合数是多少。
输入格式
仅一行，包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示怪物的 HP。
输出格式
输出一行，包含一个整数，表示在最优策略下击败怪物所需期望回合数对 $998\,244\,353$ 取模的结果。
更准确地说，如果答案的最简分数形式为 $\frac{p}{q}$，你需要提供满足 $qr \equiv p \pmod{998\,244\,353}$ 的最小非负整数 $r$。你可以确信这样的 $r$ 总存在。
样例
输入 1
1
输出 1
831870296
输入 2
5
输出 2
835978299
说明
在第一个样例中：
- 如果第一回合抽到水人卡，直接施放它，无论下一回合抽到什么卡，怪物都会被击败；
- 如果第一回合抽到火球卡，直接施放它，立即击败怪物；
- 如果第一回合抽到复制卡，则在后续回合中什么都不做，直到抽到水人卡或火球卡。一旦抽到水人卡，通过施放水人卡并随后施放手中任意一张卡，怪物将被击败。一旦抽到火球卡，通过立即施放火球卡，怪物将被击败。
综上所述，如果采取最优策略，击败 HP 为 1 的怪物的期望回合数为 $\frac{11}{6}$。