/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
長さ N の数列 A=(A_1,\ldots,A_N) が与えられます．ここで N は 3 以上の整数です．
あなたは以下の操作を 0 回以上任意の回数行うことができます．
- 1\leq i\leq N かつ A_i=A_{i+1}=A_{i+2} を満たす整数 i を選ぶ．A_i,A_{i+1},A_{i+2} のうちいずれか 2 つをそれぞれ 1 以上 N 以下の整数で置き換える．ここで，A_{N+1}=A_1,A_{N+2}=A_2 とする．
最終的に得られる A のうち，A が (1,\ldots,N) の順列であるものの個数を 998244353 で割ったあまりを求めてください．
制約
- 入力される数値は全て整数
- 3\leq N\leq 5\times 10^5
- 1\leq A_i\leq N
入力
入力は以下の形式で標準入力から与えられる．
N A_1 \ldots A_N
出力
答えを出力せよ．
入力例 1
6 1 2 3 3 1 1
出力例 1
360
例えば，最終的に A=(1,2,4,3,5,6) という順列を以下の手順で得ることができます．
- i=5 として操作を行う．A_5 を 3 で，A_6 を 6 で置き換える．A=(1,2,3,3,3,6) となる．
- i=3 として操作を行う．A_3 を 4 で，A_5 を 5 で置き換える．A=(1,2,4,3,5,6) となる．
最終的に得られる A であって (1,\ldots,6) の順列であるものの個数は 360 個です．
入力例 2
5 3 1 3 4 1
出力例 2
0
最終的に得られる A であって (1,\ldots,5) の順列であるものは存在しません．
入力例 3
10 1 1 1 8 8 8 7 7 7 10
出力例 3
604800
Score : 1000 points
Problem Statement
You are given a sequence A = (A_1, \ldots, A_N) of length N. Here, N is an integer not less than 3.
You can perform the following operation any number of times (zero or more).
- Choose an integer i satisfying 1 \leq i \leq N and A_i = A_{i+1} = A_{i+2}. Replace two of A_i, A_{i+1}, and A_{i+2} with integers between 1 and N, inclusive. Here, assume A_{N+1} = A_1 and A_{N+2} = A_2.
Find the number, modulo 998244353, of possible resulting sequences A that are permutations of (1, \ldots, N).
Constraints
- All input numbers are integers.
- 3 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq N
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
6 1 2 3 3 1 1
Sample Output 1
360
For example, we can obtain the permutation A = (1,2,4,3,5,6) through the following steps.
- Perform the operation with i=5. Replace A_5 with 3 and A_6 with 6. Now, A = (1,2,3,3,3,6).
- Perform the operation with i=3. Replace A_3 with 4 and A_5 with 5. Now, A = (1,2,4,3,5,6).
There are 360 possible resulting sequences A that are permutations of (1, \ldots, 6).
Sample Input 2
5 3 1 3 4 1
Sample Output 2
0
There are no possible resulting sequences A that are permutations of (1, \ldots, 5).
Sample Input 3
10 1 1 1 8 8 8 7 7 7 10
Sample Output 3
604800