{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $A = (A_1, \\ldots, A_N)$ of length $N$. Here, $N$ is an integer not less than $3$.\nYou can perform the following operation any number of times (zero or more).\n\n*   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$.\n\nFind the number, modulo $998244353$, of possible resulting sequences $A$ that are permutations of $(1, \\ldots, N)$."},{"iden":"constraints","content":"*   All input numbers are integers.\n*   $3 \\leq N \\leq 5 \\times 10^5$\n*   $1 \\leq A_i \\leq N$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ \n$A_1$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"6\n1 2 3 3 1 1"},{"iden":"sample output 1","content":"360\n\nFor example, we can obtain the permutation $A = (1,2,4,3,5,6)$ through the following steps.\n\n*   Perform the operation with $i=5$. Replace $A_5$ with $3$ and $A_6$ with $6$. Now, $A = (1,2,3,3,3,6)$.\n*   Perform the operation with $i=3$. Replace $A_3$ with $4$ and $A_5$ with $5$. Now, $A = (1,2,4,3,5,6)$.\n\nThere are $360$ possible resulting sequences $A$ that are permutations of $(1, \\ldots, 6)$."},{"iden":"sample input 2","content":"5\n3 1 3 4 1"},{"iden":"sample output 2","content":"0\n\nThere are no possible resulting sequences $A$ that are permutations of $(1, \\ldots, 5)$."},{"iden":"sample input 3","content":"10\n1 1 1 8 8 8 7 7 7 10"},{"iden":"sample output 3","content":"604800"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}