AT_arc187_e [ARC187E] Replace Triplets

给定序列 $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$