Circular Tree Embedding

AtCoder

IDarc199_c

Time2000ms

Memory256MB

Difficulty—

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 $(1,2,\ldots,N)$ satisfy the following condition, the permutation $Q$ is called a **good permutation** of tree $T$: > 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. You 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)$. Find the number, modulo $998244353$, of $N$\-vertex trees such that $P^1,P^2,\ldots,P^M$ are all good permutations. ## Constraints * $2\leq N,M\leq 500$ * $P^1,P^2,\ldots,P^M$ are permutations of $(1,2,\ldots,N)$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $P^1_1$ $P^1_2$ $\ldots$ $P^1_N$ $P^2_1$ $P^2_2$ $\ldots$ $P^2_N$ $\vdots$ $P^M_1$ $P^M_2$ $\ldots$ $P^M_N$ [samples]

Samples

Input #1

4 2
1 4 2 3
3 1 4 2

Output #1

8

For example, for the following two trees, both $P^1,P^2$ are good permutations. (The blue numbers represent vertex numbers.)
![image](https://img.atcoder.jp/arc199/9f18f81fa8fb939d65e4d941450a2dbf.png)
On the other hand, for the following tree, $P^2$ is not a good permutation.
![image](https://img.atcoder.jp/arc199/6b602382a1f4bc4e7d6f792c0b2f7d20.png)
There are $8$ four-vertex trees in total such that both $P^1,P^2$ are good permutations.

Input #2

12 3
7 9 1 10 8 12 2 6 11 5 4 3
8 10 4 12 11 7 6 3 1 2 9 5
10 4 9 7 5 1 3 11 8 12 6 2

Output #2

API Response (JSON)

{
  "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 $(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments