{"problem":{"name":"Replace Triplets","description":{"content":"You are given a sequence $A = (A_1, \\ldots, A_N)$ of length $N$. Here, $N$ is an integer not less than $3$. You can perform the following operation any number of times (zero or more). *   Choose an i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc187_e"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   All input numbers are integers.\n*   $3 \\leq N \\leq 5 \\times 10^5$\n*   $1 \\leq A_i \\leq N$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ \n$A_1$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc187_e","tags":[],"sample_group":[["6\n1 2 3 3 1 1","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)$."],["5\n3 1 3 4 1","0\n\nThere are no possible resulting sequences $A$ that are permutations of $(1, \\ldots, 5)$."],["10\n1 1 1 8 8 8 7 7 7 10","604800"]],"created_at":"2026-03-03 11:01:14"}}