字符序列(加强版)

提交数: 10, 平均分: 26

题目描述:

从三个元素的集合[ABC]中选取元素生成一个N个字符组成的序列,使得没有两个相邻字的子序列(子序列长度=2)相同。例:N = 5ABCBA是合格的,而序列ABCBCABABC是不合格的,因为其中子序列BCAB是相同的。

对于由键盘输入的N(1<=N<=1e8),求出满足条件的N个字符的序列数 mod 998244353。

输入格式:

 如题

输出格式:

 如题

样例输入:

4

样例输出:

72

提示:

原题链接

时间限制: 2000ms
空间限制: 16MB