分数: 1000 点
问题陈述
给你一个序列 A = (A_1, \ldots, A_N) 长度 N。在这里, N 是不小于的整数 3.
您可以执行以下操作任意次数(零次或多次)。
- 选择一个整数 i 满意 1 \leq i \leq N 和 A_i = A_{i+1} = A_{i+2}。替换其中两个 A_i, A_{i+1},和 A_{i+2} 之间的整数 1 和 N,包括在内。这里,假设 A_{N+1} = A_1 和 A_{N+2} = A_2.
求模数 998244353,可能的结果序列 A 是以下排列 (1, \ldots, N).
约束
- 所有输入数字均为整数。
- 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).
有 360 可能的结果序列 A 是以下排列 (1, \ldots, 6).
示例输入 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