Kosare

Ο Mirko βρήκε ~N~ κουτιά με διάφορα ξεχασμένα παιχνίδια στη σοφίτα του. Υπάρχουν ~M~ διαφορετικά παιχνίδια, με αρίθμηση από το ~1~ έως το ~M~, αλλά καθένα από αυτά μπορεί να εμφανιστεί πολλές φορές σε διάφορα κουτιά.

Ο Mirko αποφάσισε ότι θα διαλέξει μερικά κουτιά με τέτοιο τρόπο ώστε να υπάρχει τουλάχιστον ένα παιχνίδι από κάθε είδος και να πετάξει τα υπόλοιπα κουτιά.

Προσδιορίστε τον αριθμό των τρόπων με τους οποίους ο Mirko μπορεί να το κάνει αυτό.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~N~ και ~M\;(1 \leq N \leq 1\,000\,000,\;1 \leq M \leq 20)~.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει έναν ακέραιο ~K_i\;(0 \leq K_i \leq M)~ ακολουθούμενο από ~K_i~ διακριτούς ακέραιους αριθμούς από το διάστημα ~[1,\;M]~, που αντιπροσωπεύει τα παιχνίδια σε αυτό το πλαίσιο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου θα πρέπει να περιέχει τον απαιτούμενο αριθμό τρόπων modulo (το υπόλοιπο της διαίρεσης με) ~1\,000\,000\,007~.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, θα ισχύουν ~N \leq 100~ και ~M \leq 15~.

Σε περιπτώσεις δοκιμής αξίας ~70~% των συνολικών πόντων, θα ισχύουν ~N \leq 1\,000\,000~ και ~M \leq 15~.

Παραδείγματα

input

3 3
3 1 2 3
3 1 2 3
3 1 2 3

output

7

input

3 3
1 1
1 2
1 3

output

1

input

4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5

output

6