题目描述

给定一个正整数 $N$。请计算满足以下条件的长度为 $3N$ 的数列 $A$ 的个数，并将结果对 $998244353$ 取模后输出。

• $A$ 中每个 $1$ 到 $N$ 的整数恰好各出现 $3$ 次。
• $A$ 的任意长度为 $N$ 的连续子序列都不是数列 $(1, 2, \ldots, N)$ 的一个排列。

输入格式

输入为标准输入，格式如下：

$N$

输出格式

输出答案。

样例 1

输入

3

输出

132

样例 2

输入

123456

输出

31984851

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• 输入均为整数

样例解释 1

例如，$A = (1, 3, 3, 2, 2, 2, 1, 1, 3)$ 满足题目中的条件。而 $A = (1, 3, 3, 2, 2, 3, 1, 1, 2)$ 不满足条件，因为 $A$ 的第 $5, 6, 7$ 个元素组成的连续子序列是数列 $(1, 2, 3)$ 的一个排列。

由 ChatGPT 4.1 翻译