Universal Cup Judging System

Universal Cup

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

未知の根付き木の $m$ 個の深さ優先探索(DFS)順序が与えられます。

$1$ から $n$ までの番号が付けられた $n$ 個の頂点を持つ根付き木を考えます。ここで頂点 $1$ が根です。この木は無向かつ連結であり、ちょうど $n - 1$ 本の辺を持ちます。

DFS の定義。 固定された根付き木に対して、DFS 順序は次のようにして得られます:

  • すべての頂点は最初、未訪問である。
  • 根 $1$ から開始し、訪問済みの印をつけ、それを出力する。
  • ある頂点 $v$ にいるとき、根付き木における $v$ のすべての子を考える。その子を任意の順序で選ぶ。選ばれた各子 $u$ について、まだ未訪問であれば $u$ に移動し、訪問済みの印をつけ、$u$ を出力し、同様に $u$ から DFS を続ける。

固定された木に対して、各頂点の子を処理する順序の選び方が異なると、異なる DFS 順序が生成されることがあります。すべての DFS 順序は $1, 2, \dots, n$ の順列であり、常に $1$ から始まります。

先頭が $1$ である $1, 2, \dots, n$ の順列が $m$ 個与えられます。これらはすべて、上で定義された意味での同じ根付き木(根は $1$)の DFS 順序であることが分かっています(ただし、異なる DFS の実行では子の順序の選び方が異なる可能性があります)。

あなたの課題は、これら $m$ 個の DFS 順序をすべて生成しうる異なる根付き木が何通りあるかを求めることです。

$2$ つの根付き木は、それらの辺集合異なるときに異なるとみなされます。

答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

$1$ 行目には $2$ つの整数 $n$ と $m$($1 \le n, m \le 500$)が含まれます。

続く $m$ 行のそれぞれには、$k$ 番目の DFS 順序を表す整数 $1, 2, \dots, n$ の順列 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ が含まれます。

すべての $k$ について、$p_{k,i}$ はすべて異なり、かつ $p_{k,1} = 1$ です。

出力

頂点集合が $1, 2, \dots, n$ で根が $1$ である根付き木のうち、与えられたすべての列がその木の有効な DFS 順序となるものの個数を $10^9 + 7$ で割った余りを、単一の整数として出力してください。

入出力例

3 2
1 2 3
1 3 2
1
4 1
1 2 3 4
5
5 2
1 2 3 4 5
1 2 4 3 5
3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.