琼玉牌

题目描述

奶龙正在玩「帝垣琼玉」牌。

「帝垣琼玉」牌有 $3$ 种不同花色的琼玉牌，奶龙的桌子上有 $4$ 个放牌的位置，最开始奶龙的牌桌上没有琼玉牌。

奶龙会进行 $n$ 回合的抽牌。每个回合开始时，奶龙会从牌堆里立即随机抽取 $2$ 次牌 (牌堆里每种牌都有无穷多张，每次抽上来三种牌的概率相同，同一回合抽上来的两张牌花色可能一样) 。但奶龙最多持有 $4$ 张牌，如果奶龙当前持有的牌数大于 $4$ ,奶龙就需要弃掉一些牌，使得牌桌上的牌恰好剩余 $4$ 张。

奶龙十分聪明，会采取当前最优的策略来弃牌。假设弃牌后三种牌的剩余数量分别为 $A,B,C$ ，那么在所有弃牌方案中，奶龙会选择：

1.$A,B,C$ 中的最大值尽可能大。

2.在满足第一条的基础上，$A,B,C$ 的次大值尽可能大。

的一种弃牌方案。如果此时有多种弃牌后的方案都满足这个条件，则奶龙会选择任意一种。

例如，假设一次摸牌后三种牌剩余数量为 $\{2,1,3\}$，那么弃牌后奶龙剩余的三种牌数为 $\{1,0,3\}$ .

摸牌并弃完牌后，若奶龙持有的琼玉牌数为 $4$ 且花色全部相同，那么奶龙就会消耗掉自己所有的琼玉牌，并触发一次【暗杠】，此时牌桌上剩余的牌数变为 $0$.

现在，奶龙希望你帮它算出，它摸 $n$ 回合牌，期望会触发多少次【暗杠】。奶龙觉得过大的数字很麻烦，所以你只需要告诉它答案模 $998244353$ 后的结果即可。

输入格式

一行，输入一个整数 $n$ ,表示奶龙摸牌的回合数。

输出格式

一行，输出一个整数，表示奶龙期望触发【暗杠】的次数。

答案对 $998244353$ 取模。

样例 #1

样例输入 #1

2

样例输出 #1

480636170

样例 #2

样例输入 #2

3

样例输出 #2

460096163

样例 #3

样例输入 #3

4

样例输出 #3

760436714

提示

样例 $1$ 解释：

奶龙两回合摸牌的可能性有 $3^4$ 种，其中有 $3$ 种能使奶龙摸触发一次【暗杠】，所以期望次数为 $\frac{1}{27}$.

数据范围：

对于 $20\%$ 的数据，满足 $n \le 6$.

对于 $40\%$ 的数据，满足 $n \le 1000$.

对于 $60\%$ 的数据，满足 $n \le 10^6$.

对于 $80\%$ 的数据，满足 $n \le 10^{18}$.

对于 $100\%$ 的数据，满足 $n \le 10^{100000}$.