/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 1700 点
問題文
正整数 N が与えられます。 1 以上 N 以下の整数をそれぞれ 3 個ずつ含む長さ 3N の数列 A であって、 下記の条件を満たすものの個数を 998244353 で割った余りを出力してください。
- A の長さ N のどの連続部分列も、数列 (1, 2, \ldots, N) の順列ではない。
制約
- 1 \leq N \leq 2 \times 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
132
例えば、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) の順列であるからです。
入力例 2
123456
出力例 2
31984851
Score : 1700 points
Problem Statement
You are given a positive integer N. Print the number, modulo 998244353, of sequences A of length 3N that contain each integer from 1 through N three times and satisfy the following condition.
- A has no contiguous subsequence of length N that is a permutation of the sequence (1, 2, \ldots, N).
Constraints
- 1 \leq N \leq 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
132
For instance, A = (1, 3, 3, 2, 2, 2, 1, 1, 3) satisfies the condition in the problem statement. On the other hand, A = (1, 3, 3, 2, 2, 3, 1, 1, 2) does not, because the 5-th, 6-th, 7-th elements of A form a contiguous subsequence that is a permutation of the sequence (1, 2, 3).
Sample Input 2
123456
Sample Output 2
31984851