Сізге белгісіз түбірлі ағаштың тереңдігі бойынша іздеудің (DFS) $m$ реті берілген.
Біз $1$-ден $n$-ге дейін нөмірленген $n$ төбесі бар түбірлі ағаштарды қарастырамыз, мұндағы $1$-ші төбе — түбір. Ағаш бағытталмаған және байланысқан, әрі оның дәл $n - 1$ қыры бар.
DFS анықтамасы. Бекітілген түбірлі ағаш үшін DFS реті келесідей алынады:
- Бастапқыда барлық төбелер қаралмаған күйде болады.
- $1$-ші түбірден бастап, оны қаралды деп белгілеп, оны шығарыңыз.
- Қандай да бір $v$ төбесінде тұрғанда, түбірлі ағаштағы $v$ төбесінің барлық балаларын қарастырыңыз. Оның балаларын кез келген ретпен таңдаңыз. Әлі қаралмаған әрбір таңдалған $u$ баласы үшін $u$-ға өтіп, оны қаралды деп белгілеп, $u$-ды шығарыңыз да, дәл солай $u$-дан DFS-ті жалғастырыңыз.
Бекітілген ағаш үшін әрбір төбенің балаларын өңдеу ретін әртүрлі таңдау әртүрлі DFS реттерін беруі мүмкін. Барлық DFS реттері $1, 2, \dots, n$ сандарының орын ауыстырулары болып табылады және әрқашан $1$-ден басталады.
Сізге әрқайсысы $1$-ден басталатын $1, 2, \dots, n$ сандарының $m$ орын ауыстыруы берілген. Олардың әрқайсысы жоғарыда анықталған мағынада бір ғана түбірлі ағаштың (түбірі $1$) DFS реті екені белгілі (әртүрлі DFS іске қосуларында балалар реті әртүрлі таңдалуы мүмкін).
Сіздің міндетіңіз — осы $m$ DFS ретінің барлығын бере алатын қанша әртүрлі түбірлі ағаш бар екенін анықтау.
Екі түбірлі ағаштың қырлар жиындары әртүрлі болса, олар әртүрлі деп есептеледі.
Жауап өте үлкен болуы мүмкін болғандықтан, оны $10^9 + 7$ модулі бойынша шығаруыңыз керек.
Кіріс деректер
Бірінші жолда екі бүтін сан $n$ және $m$ ($1 \le n, m \le 500$) берілген.
Келесі $m$ жолдың әрқайсысында $k$-шы DFS ретін сипаттайтын $1, 2, \dots, n$ бүтін сандарының $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ орын ауыстыруы берілген.
Әрбір $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