Universal Cup Judging System

Universal Cup

Límite de tiempo: 3 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Anda diberikan $m$ urutan pencarian mendalam (depth-first search / DFS) dari sebuah pohon berakar yang tidak diketahui.

Kita meninjau pohon berakar dengan $n$ simpul yang diberi label dari $1$ hingga $n$, dengan simpul $1$ sebagai akarnya. Pohon tersebut tak berarah dan terhubung, serta memiliki tepat $n - 1$ sisi.

Definisi DFS. Untuk sebuah pohon berakar yang tetap, sebuah urutan DFS diperoleh sebagai berikut:

  • Semua simpul pada awalnya belum dikunjungi.
  • Mulai dari akar $1$, tandai sebagai sudah dikunjungi dan keluarkan simpul tersebut.
  • Ketika Anda berada di suatu simpul $v$, tinjau semua anak dari $v$ pada pohon berakar tersebut. Pilih anak-anaknya dalam urutan apa pun. Untuk setiap anak $u$ terpilih yang masih belum dikunjungi, pergi ke $u$, tandai sebagai sudah dikunjungi, keluarkan $u$, dan lanjutkan DFS dari $u$ dengan cara yang sama.

Untuk sebuah pohon yang tetap, pilihan urutan pemrosesan anak dari setiap simpul yang berbeda dapat menghasilkan urutan DFS yang berbeda. Semua urutan DFS merupakan permutasi dari $1, 2, \dots, n$ dan selalu dimulai dengan $1$.

Anda diberikan $m$ permutasi dari $1, 2, \dots, n$, masing-masing dimulai dengan $1$. Diketahui bahwa masing-masing permutasi tersebut adalah urutan DFS dari pohon berakar yang sama (dengan akar $1$) sesuai definisi di atas (mungkin menggunakan pilihan urutan anak yang berbeda untuk jalannya DFS yang berbeda).

Tugas Anda adalah menentukan berapa banyak pohon berakar berbeda yang dapat menghasilkan semua $m$ urutan DFS ini.

Dua pohon berakar dianggap berbeda jika himpunan sisinya berbeda.

Karena jawabannya bisa sangat besar, Anda harus mengeluarkan hasilnya modulo $10^9 + 7$.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n, m \le 500$).

Masing-masing dari $m$ baris berikutnya berisi sebuah permutasi $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ dari bilangan bulat $1, 2, \dots, n$, yang mendeskripsikan urutan DFS ke-$k$.

Untuk setiap $k$, semua $p_{k,i}$ saling berbeda dan $p_{k,1} = 1$.

Keluaran

Keluarkan sebuah bilangan bulat tunggal: banyaknya pohon berakar dengan himpunan simpul $1, 2, \dots, n$ dan akar $1$ yang membuat setiap barisan yang diberikan merupakan urutan DFS yang valid dari pohon tersebut, diambil modulo $10^9 + 7$.

Contoh

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.