تُعطى لك $m$ من ترتيبات البحث في العمق أولاً (DFS) لشجرة مجذّرة غير معروفة.
نعتبر الأشجار المجذّرة التي تحتوي على $n$ من الرؤوس المرقمة من $1$ إلى $n$، حيث الرأس $1$ هو الجذر. الشجرة غير موجهة ومترابطة، ولها بالضبط $n - 1$ من الأضلاع.
تعريف DFS. بالنسبة لشجرة مجذّرة ثابتة، يتم الحصول على ترتيب DFS كما يلي:
- جميع الرؤوس غير مزورة في البداية.
- ابدأ عند الجذر $1$، وعلّمه كمزور واطبعه.
- عندما تكون عند رأس ما $v$، خذ بعين الاعتبار جميع أبناء $v$ في الشجرة المجذّرة. اختر أبناءه بـ أي ترتيب. لكل ابن مختار $u$ لا يزال غير مزور، انتقل إلى $u$، وعلّمه كمزور، واطبع $u$، وتابع DFS من $u$ بنفس الطريقة.
بالنسبة لشجرة ثابتة، قد تؤدي الاختيارات المختلفة للترتيب الذي تتم به معالجة أبناء كل رأس إلى إنتاج ترتيبات DFS مختلفة. جميع ترتيبات DFS هي تبديلات للأعداد $1, 2, \dots, n$ وتبدأ دائماً بالعدد $1$.
تُعطى لك $m$ من التبديلات للأعداد $1, 2, \dots, n$، يبدأ كل منها بالعدد $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