{"raw_statement":[{"iden":"problem statement","content":"In this problem, we simply call a tree with $N$ vertices numbered $1,2,\\ldots,N$ and unnumbered edges an $N$\\-vertex tree.\nWhen an $N$\\-vertex tree $T$ and a permutation $Q=(Q_1,Q_2,\\ldots,Q_N)$ of $(1,2,\\ldots,N)$ satisfy the following condition, the permutation $Q$ is called a **good permutation** of tree $T$:\n\n> There are $N$ points $1,2,\\ldots,N$ arranged counterclockwise at equal intervals on a circle in this order. For each edge $\\lbrace u,v\\rbrace$ of tree $T$, draw a line segment connecting the two points $Q_u,Q_v$. Then, among the $N-1$ line segments drawn, no two of them have a common point except at their endpoints.\n\nYou are given $M$ permutations of $(1,2,\\ldots,N)$: $P^1=(P^1_1,P^1_2,\\ldots,P^1_N),P^2=(P^2_1,P^2_2,\\ldots,P^2_N),\\ldots,P^M=(P^M_1,P^M_2,\\ldots,P^M_N)$.\nFind the number, modulo $998244353$, of $N$\\-vertex trees such that $P^1,P^2,\\ldots,P^M$ are all good permutations."},{"iden":"constraints","content":"*   $2\\leq N,M\\leq 500$\n*   $P^1,P^2,\\ldots,P^M$ are permutations of $(1,2,\\ldots,N)$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$P^1_1$ $P^1_2$ $\\ldots$ $P^1_N$\n$P^2_1$ $P^2_2$ $\\ldots$ $P^2_N$\n$\\vdots$\n$P^M_1$ $P^M_2$ $\\ldots$ $P^M_N$"},{"iden":"sample input 1","content":"4 2\n1 4 2 3\n3 1 4 2"},{"iden":"sample output 1","content":"8\n\nFor example, for the following two trees, both $P^1,P^2$ are good permutations. (The blue numbers represent vertex numbers.)\n![image](https://img.atcoder.jp/arc199/9f18f81fa8fb939d65e4d941450a2dbf.png)\nOn the other hand, for the following tree, $P^2$ is not a good permutation.\n![image](https://img.atcoder.jp/arc199/6b602382a1f4bc4e7d6f792c0b2f7d20.png)\nThere are $8$ four-vertex trees in total such that both $P^1,P^2$ are good permutations."},{"iden":"sample input 2","content":"12 3\n7 9 1 10 8 12 2 6 11 5 4 3\n8 10 4 12 11 7 6 3 1 2 9 5\n10 4 9 7 5 1 3 11 8 12 6 2"},{"iden":"sample output 2","content":"540"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}