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