{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$. Print the number, modulo $998244353$, of sequences $A$ of length $3N$ that contain each integer from $1$ through $N$ three times and satisfy the following condition.\n\n*   $A$ has no contiguous subsequence of length $N$ that is a permutation of the sequence $(1, 2, \\ldots, N)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$"},{"iden":"sample input 1","content":"3"},{"iden":"sample output 1","content":"132\n\nFor instance, $A = (1, 3, 3, 2, 2, 2, 1, 1, 3)$ satisfies the condition in the problem statement. On the other hand, $A = (1, 3, 3, 2, 2, 3, 1, 1, 2)$ does not, because the $5$\\-th, $6$\\-th, $7$\\-th elements of $A$ form a contiguous subsequence that is a permutation of the sequence $(1, 2, 3)$."},{"iden":"sample input 2","content":"123456"},{"iden":"sample output 2","content":"31984851"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}