{"problem":{"name":"Circular Tree Embedding","description":{"content":"In this problem, we simply call a tree with $N$ vertices numbered $1,2,\\ldots,N$ and unnumbered edges an $N$\\-vertex tree. When an $N$\\-vertex tree $T$ and a permutation $Q=(Q_1,Q_2,\\ldots,Q_N)$ of $(","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc199_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc199_c","tags":[],"sample_group":[["4 2\n1 4 2 3\n3 1 4 2","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."],["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","540"]],"created_at":"2026-03-03 11:01:13"}}