{"raw_statement":[{"iden":"problem statement","content":"Snuke has come up with the following problem.\n\n> You are given permutations $P=(P_1,P_2,\\ldots,P_N)$ and $Q=(Q_1,Q_2,\\ldots,Q_N)$ of $(1,2,\\ldots,N)$. Let us build a graph with $N$ vertices and $N$ edges as follows.\n> \n> *   For $i=1,2,\\ldots,N$ in this order, draw an edge of weight $Q_i$ connecting vertices $i$ and $P_i$ bidirectionally.\n> \n> When removing some number of edges to eliminate cycles from the graph, find the minimum possible total weight of the removed edges.\n\nAlice and Bob came up with the following solutions.\n**Alice:** Initialize the answer to $0$. For $i=1,2,\\ldots,N$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer.\n**Bob:** Initialize the answer to $0$. For $i=N,N-1,\\ldots,1$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer.\nSnuke has realized that their solutions are both incorrect, and he wants to know the number of inputs for which neither of their solutions gives the correct answer.\nAmong the $(N!)^2$ possible inputs, find the number, modulo $998244353$, of inputs for which neither Alice's nor Bob's solution gives the correct answer."},{"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":"4\n\nThe following four inputs satisfy the condition.\n\n*   $P=(2,3,1),Q=(2,1,3)$\n*   $P=(2,3,1),Q=(3,1,2)$\n*   $P=(3,1,2),Q=(2,1,3)$\n*   $P=(3,1,2),Q=(3,1,2)$\n\nFor example, for the input $P=(2,3,1),Q=(2,1,3)$, the correct answer is $1$, but Alice's solution gives $2$ and Bob's gives $3$."},{"iden":"sample input 2","content":"2"},{"iden":"sample output 2","content":"0\n\nThere may be no inputs that satisfy the condition."},{"iden":"sample input 3","content":"6"},{"iden":"sample output 3","content":"314708"},{"iden":"sample input 4","content":"318"},{"iden":"sample output 4","content":"321484323"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}