คุณจะได้รับลำดับการค้นหาแบบลึกก่อน (DFS) จำนวน $m$ ลำดับของต้นไม้มีรากที่ไม่ทราบโครงสร้างต้นหนึ่ง
เราพิจารณาต้นไม้มีรากที่มีจุดยอด $n$ จุด ซึ่งมีหมายเลขตั้งแต่ $1$ ถึง $n$ โดยที่จุดยอด $1$ เป็นราก ต้นไม้นี้ไม่มีทิศทางและเชื่อมต่อกัน และมีเส้นเชื่อมอยู่ $n - 1$ เส้นพอดี
นิยามของ DFS สำหรับต้นไม้มีรากที่กำหนดไว้ตายตัวต้นหนึ่ง ลำดับ DFS จะหาได้ดังนี้:
- จุดยอดทั้งหมดเริ่มต้นในสถานะยังไม่ถูกเยี่ยมชม
- เริ่มต้นที่ราก $1$ ทำเครื่องหมายว่าเยี่ยมชมแล้ว และ แสดงผล ออกมา
- เมื่อคุณอยู่ที่จุดยอด $v$ ใดๆ ให้พิจารณาจุดยอดลูกทั้งหมดของ $v$ ในต้นไม้มีราก เลือกจุดยอดลูกของมันในลำดับ ใดก็ได้ สำหรับจุดยอดลูก $u$ แต่ละตัวที่ถูกเลือกและยังไม่ถูกเยี่ยมชม ให้เดินไปยัง $u$ ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงผล $u$ และดำเนินการ DFS ต่อจาก $u$ ด้วยวิธีเดียวกัน
สำหรับต้นไม้ที่กำหนดไว้ตายตัว การเลือกลำดับในการประมวลผลจุดยอดลูกของแต่ละจุดยอดที่แตกต่างกันอาจทำให้เกิดลำดับ DFS ที่แตกต่างกันได้ ลำดับ DFS ทั้งหมดเป็นเรียงสับเปลี่ยนของ $1, 2, \dots, n$ และเริ่มต้นด้วย $1$ เสมอ
คุณจะได้รับเรียงสับเปลี่ยนของ $1, 2, \dots, n$ จำนวน $m$ ชุด ซึ่งแต่ละชุดเริ่มต้นด้วย $1$ คุณทราบว่าแต่ละชุดเป็นลำดับ DFS ของต้นไม้มีราก ต้นเดียวกัน (ที่มีรากคือ $1$) ตามความหมายที่นิยามไว้ข้างต้น (โดยอาจใช้การเลือกลำดับจุดยอดลูกที่แตกต่างกันในการรัน DFS แต่ละครั้ง)
งานของคุณคือการหาว่ามีต้นไม้มีรากที่แตกต่างกันกี่ต้นที่สามารถสร้างลำดับ DFS ทั้ง $m$ ลำดับนี้ได้ ทั้งหมด
ต้นไม้มีรากสองต้นจะถือว่าแตกต่างกันหากเซตของเส้นเชื่อมของทั้งสองต้นแตกต่างกัน
เนื่องจากคำตอบอาจมีค่ามาก คุณจึงควรแสดงผลคำตอบมอดูโล $10^9 + 7$
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n$ และ $m$ ($1 \le n, m \le 500$)
ใน $m$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยเรียงสับเปลี่ยน $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ ของจำนวนเต็ม $1, 2, \dots, n$ ซึ่งอธิบายลำดับ DFS ลำดับที่ $k$
สำหรับทุกค่า $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