Universal Cup Judging System

Universal Cup

حد الوقت: 3 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

畀定一棵未知有根樹嘅 $m$ 個深度優先搜尋(DFS)序。

我哋考慮包含 $n$ 個頂點(編號由 $1$ 到 $n$)嘅有根樹,其中頂點 $1$ 係根。呢棵樹係無向連通嘅,而且恰好有 $n - 1$ 條邊。

DFS 嘅定義。 對於一棵固定嘅有根樹,佢嘅 DFS 序係透過以下方式獲得:

  • 所有頂點一開始都係未訪問狀態。
  • 由根節點 $1$ 開始,將佢標記為已訪問並輸出佢。
  • 當你位於某個頂點 $v$ 嗰陣,考慮呢棵有根樹入面 $v$ 嘅所有子節點。以任意順序揀佢嘅子節點。對於每個揀中而且仲未訪問嘅子節點 $u$,移動到 $u$,將佢標記為已訪問,輸出 $u$,然後用同樣嘅方式由 $u$ 繼續進行 DFS。

對於一棵固定嘅樹,處理每個頂點嘅子節點嘅唔同順序可能會產生唔同嘅 DFS 序。所有 DFS 序都係 $1, 2, \dots, n$ 嘅排列,而且總係以 $1$ 開頭。

畀定 $m$ 個 $1, 2, \dots, n$ 嘅排列,每個排列都以 $1$ 開頭。已知佢哋全部都係同一棵有根樹(以 $1$ 為根)喺上述定義下嘅 DFS 序(喺唔同嘅 DFS 過程入面可能用咗唔同嘅子節點順序)。

你嘅任務係確定有幾多棵唔同嘅有根樹可以產生呢 $m$ 個 DFS 序嘅全部。

如果兩棵有根樹嘅邊集唔同,就認為佢哋係唔同嘅。

由於答案可能非常大,你應該輸出佢對 $10^9 + 7$ 取模之後嘅結果。

輸入格式

第一行包含兩個整數 $n$ 同埋 $m$($1 \le n, m \le 500$)。

接落嚟嘅 $m$ 行,每行包含一個整數 $1, 2, \dots, n$ 嘅排列 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$,描述第 $k$ 個 DFS 序。

對於每個 $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.