Bi-ing Lottery Treekets

Σε ένα παράλληλο σύμπαν, όλοι σκόραραν τέλεια στον CCO. Ως εκ τούτου, ο Troy πρέπει να διαλέξει τον νικητή μέσα από μια λοταρία. Κάθε διαγωνιζόμενος θα διαλέξει αριθμούς για να δημιουργήσει έναν λαχνό. Ένας λαχνός είναι ένας πίνακας (array) μεγέθους ~N~ αριθμημένος από το ~1~ έως το ~N~ όπου κάθε καταχώριση στον πίνακα είναι ένας αριθμός από το ~0~ έως το ~K~.

Ο νικητήριος λαχνός καθορίζεται πετώντας ~K~ μπαλάκια (αριθμημένα από το ~1~ έως το ~K~) με τυχαία σειρά σε ένα δυαδικό δέντρο με ρίζα (rooted binary tree). Το δέντρο έχει ~N~ κόμβους (αριθμημένους από το ~1~ έως το ~N~) και έχει ως ρίζα τον κόμβο ~1~.

Κάθε μπαλάκι έχει έναν καθορισμένο κόμβο ρίψης στον οποίο θα ριφθεί. Όταν ένα μπαλάκι ριφθεί σε έναν άδειο κόμβο ή εισέλθει σε έναν άδειο κόμβο, θα συμβεί ένα από τρία πράγματα:

  ~1~. Εάν όλα από τα "παιδιά" του κόμβου είναι κατειλημμένα από μπαλάκια (ή αν ένας κόμβος δεν έχει "παιδιά"),
  το τρέχον μπαλάκι μένει στον τρέχον κόμβο. Δηλαδή, παραμένει εκεί και δεν μετακινείται ξανά.

  ~2~. Εάν ο τρέχον κόμβος έχει μόνο ένα άδειο "παιδί", το τρέχον μπαλάκι θα μετακινηθεί σε εκείνο το "παιδί".

  ~3~. Εάν ο τρέχον κόμβος έχει δύο άδεια "παιδιά" και αν το τρέχον μπαλάκι ρίφθηκε, θα μπορούσε να πάει είτε
  αριστερά είτε δεξιά. Ειδάλλως, θα συνεχίσει προς την κατεύθυνση της προηγούμενής του κίνησης.

Εάν δεν μπορούν να ριφθούν όλα τα ~K~ μπαλάκια, δεν γίνεται να καθοριστεί ο νικητήριος λαχνός. Αυτό συμβαίνει όταν ένα μπαλάκι ριφθεί και ο κόμβος ρίψης του είναι κατηλλημένος από ένα άλλο μπαλάκι.

Εάν ριφθούν όλα τα ~K~ μπαλάκια, οι θέσεις στις οποίες έχουν καταλήξει τα μπαλάκια καθορίζουν το νικητήριο λαχνό. Η ~i~-οστη καταχώριση του νικητήριου λαχνού είναι ο αριθμός από το μπαλάκι που βρίσκεται στον κόμβο ~i~ ή στον κόμβο ~0~ αν δεν υπάρχει κάποιο μπαλάκι στον κόμβο ~i~.

Ο Troy θα ήθελε να ξέρει τον αριθμό των πιθανών νικητήριων λαχνών (ο οποίος μπορεί να είναι και μηδέν).

Είσοδος

Η πρώτη γραμμή περιέχει δύο χωρισμένους με κενό ακέραιους αριθμούς ~N~ και ~K~, που δηλώνουν τον αριθμό των κόμβων στο δυαδικό δέντρο και τον αριθμό από μπαλάκια, αντίστοιχα.

Η επόμενη γραμμή περιέχει ~K~ χωρισμένους με κενό ακέραιους αριθμούς, όπου ο ~i~-στος ακέραιος δηλώνει τον καθορισμένο κόμβο ρίψης από το μπαλάκι με τον αριθμό ~i~.

Οι τελευταίες ~N~ γραμμές περιέχουν η καθεμία δύο χωρισμένους με κενό ακέραιους αριθμούς. Η ~i~-οστη γραμμή περιέχει το ~L_i~ και το ~R_i~ που δηλώνουν το αριστερό και το δεξί "παιδί" του ~i~-οστου κόμβου αντίστοιχα, όπου ~0~ σημαίνει ότι δεν υπάρχει τέτοιο "παιδί".

Βαθμολογία

Βαθμοί	Περιορισμοί στο ~N~	Περιορισμοί στο ~K~	Επιπλέον περιορισμοί
3	~1 \le N \le 12~	~1 \le K \le 6~	Κανένας
4	~1 \le N \le 4\,000~	~1 \le K \le 4\,000~	Όλοι οι κόμβοι δεν έχουν αριστερό "παιδί"
9	~1 \le N \le 4\,000~	~1 \le K \le 4\,000~	Οι ~N~ κόμβοι ρίψης είναι μοναδικοί
9	~1 \le N \le 4\,000~	~1 \le K \le 4\,000~	Κανένας

Έξοδος

Εκτυπώστε το υπόλοιπο της διαίρεσης του αριθμού των νικητήριων λαχνών με το ~10^9 + 7~.

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

input

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

output

4

Επεξήγηση του 1ου παραδείγματος

Το δέντρο είναι έτσι:

Θεωρήστε ότι το μπαλάκι ~1~ ρίχνεται πρώτο. Εάν το μπαλάκι ~1~ πάει αριστερά, τότε θα καταλήξει στον κόμβο ~2~. Έπειτα, θα ριφθεί το μπαλάκι ~2~ και μπορεί να καταλήξει στον κόμβο ~4~ ή ~5~. Αν το μπαλάκι ~1~ πάει δεξιά, θα καταλήξει στον κόμβο ~5~. Μετά, το μπαλάκι ~2~ θα καταλήξει στον κόμβο ~4~.

Θεωρήστε ότι το μπαλάκι ~2~ ρίχνεται πρώτο. Το μπαλάκι ~2~ μπορεί να πάει αριστερά ή δεξιά και να καταλήξει στον κόμβο ~4~ ή ~5~ αντίστοιχα. Μετά, αν το μπαλάκι ~1~ πάει αριστερά αφού ριφθεί, θα καταλήξει στον κόμβο ~2~. Ωστόσο, αν το μπαλάκι ~1~ πάει δεξιά, θα καταλήξει στον κόμβο που δεν βρίσκεται το μπαλάκι ~2~, δηλαδή είτε στον κόμβο ~4~ είτε στον κόμβο ~5~.

Οι πιθανοί νικητήριοι λαχνοί είναι ~[0,1,0,2,0]~, ~[0,1,0,0,2]~, ~[0,0,0,1,2]~ και ~[0,0,0,2,1]~.

input

4 3
1 2 4
0 2
0 3
0 4
0 0

output

2

Επεξήγηση του 2ου παραδείγματος

Το δέντρο είναι έτσι:

Αυτό το παράδειγμα ικανοποιεί το δεύτερο υποπρόβλημα.

Το μπαλάκι ~3~ πρέπει να ριφθεί πρώτο γιατί αν είτε το μπαλάκι ~1~ είτε το μπαλάκι ~2~ ριφθούν πριν από το μπαλάκι ~3~, θα κατέληγαν στον κόμβο ~4~ και δεν θα επέτρεπαν στο μπαλάκι ~3~ να ριφθεί.

Έτσι, μπορούμε είτε να ρίξουμε πρώτα το μπαλάκι ~3~, μετά το μπαλάκι ~2~ και τέλος το μπαλάκι ~1~ είτε να ρίξουμε πρώτα το μπαλάκι ~3~, μετά το μπαλάκι ~1~ και τέλος το μπαλάκι ~2~.

Οι πιθανοί νικητήριοι λαχνοί είναι ~[0,1,2,3]~ και [~0,2,1,3~].

Επίσημοι Ορισμοί

Ένα δυαδικό δέντρο είναι ένα σύνολο από κόμβους που είναι είτε άδειοι, είτε ένας κόμβος-ρίζα με ένα αριστερό υπο-δέντρο και ένα δεξί υπο-δέντρο τα οποία είναι δυαδικά δέντρα. Δεδομένου ενός κόμβου ~x~, αν το αριστερό του υπο-δέντρο δεν είναι άδειο, τότε η ρίζα αυτού του υπο-δέντρου ονομάζεται ονομάζεται αριστερό "παιδί" του ~x~. Παρομοίως, δεδομένου ενός κόμβου ~x~, αν το δεξί του υπο-δέντρο δεν είναι άδειο, τότε η ρίζα αυτού του υπο-δέντρου ονομάζεται δεξί "παιδί" του ~x~.