AT_arc187_e.[ARC187E] Replace Triplets

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定序列 $A=(A_1,A_2,\cdots,A_N)$ ，其中 $N\ge 3$ 。

你可以进行以下操作若干次：

选择整数 $i$ 满足 $1\le i\le N$ 且 $A_i=A_{i+1}=A_{i+2}$ ，将 $A_{i},A_{i+1},A_{i+2}$ 三个数中的两个替换成 $1\sim N$ 的整数。规定 $A_{N+1}=A_1$ ， $A_{N+2}=A_2$ 。

求有多少种可能到达的状态，使得恰好是 $1\sim N$ 的排列，答案 $\bmod\ 998244353$ 。

第一行一个整数 $N$ 。

第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$ 。

一个整数答案。

$3\le N\le 5\times 10^5,1\le A_i\le N$

输入解题思路，AI测评打分。不知道怎么写?