← 返回题目列表

AtCoder · arc187_e

E. 替换三元组

中文机器翻译题面 查看原题

分数: 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