Šarenlist

Ζεστή καλοκαιρινή νύχτα. Ο Vito και ο φίλος του, Karlo, είναι ξαπλωμένοι σε ένα ξέφωτο του δάσους και κοιτάνε τα αστέρια. Ξαφνικά, ο Vito αναφωνεί "Karlo, κοίτα! Τα δέντρα τριγύρω αλλάζουν χρώματα!" "Ουάου, τόσο χρώμα", είπε ο Karlo έκπληκτος. Πράγματι, τα κλαδιά των δέντρων στο δάσος άρχισαν να αλλάζουν χρώματα.

Γοητευμένοι από τα πολύχρωμα δέντρα, ο Vito και ο Karlo παρατήρησαν μερικά δεδομένα σχετικά με αυτά. Κάθε ένα από τα δέντρα που κοιτάζουν μπορεί να αναπαρασταθεί ως δενδρικός γράφος, δηλαδή ένας μη κατευθυνόμενος γράφος στον οποίο υπάρχει μία μοναδική διαδρομή μεταξύ κάθε ζεύγους κόμβων. Τα δέντρα, τα οποία κοιτάζουν, έχουν την ιδιότητα ότι κάθε κλαδί του δέντρου είναι χρωματισμένο με ένα από ~k~ διαφορετικά χρώματα. Μερικά από τα μονοπάτια στο δέντρο είναι πολύχρωμα, πράγμα που σημαίνει ότι μια τέτοια διαδρομή περιέχει κλαδιά τουλάχιστον δύο διαφορετικών χρωμάτων.

Ξημέρωσε και η μαγεία των δέντρων έχει πλέον χαθεί. Για να ξαναζήσουν αυτή την εμπειρία, ο Vito και ο Karlo σας ζητούν να λύσετε το παρακάτω πρόβλημα. Με δεδομένο ένα δέντρο και ~m~ ζεύγη κόμβων στο δέντρο, προσδιορίστε τον αριθμό διαφορετικών χρωματισμών των κλαδιών των δέντρων, έτσι ώστε καθεμία από τις ~m~ διαδρομές που καθορίζονται από τα ~m~ ζεύγη κόμβων να είναι πολύχρωμα. Δεδομένου ότι αυτός ο αριθμός μπορεί να είναι πολύ μεγάλος, δώστε το αποτέλεσμα σε μορφή modulo ~10^9 + 7~.

Είσοδος

Η πρώτη γραμμή περιέχει τρεις θετικούς ακέραιους ~n,\;m~ και ~k\;(3 \le n \le 60,\;1 \le m \le 15,\;2 \le k \le 10^9)~, τον αριθμό των κόμβων στο δέντρο, τον αριθμό διαδρομών που απαιτείται να είναι πολύχρωμες και τον αριθμό των πιθανών χρωμάτων για τα κλαδιά του δέντρου, αντίστοιχα.

Η ~i~-οστή των επόμενων ~n - 1~ γραμμών περιέχει ένα ζεύγος θετικών ακεραίων ~a_i~ και ~b_i\;(1 \le a_i,\;b_i \le n)~, που αντιπροσωπεύουν ένα κλαδί του δέντρου.

Η ~j~-οστή των επόμενων ~m~ γραμμών περιέχει ένα ζεύγος θετικών ακεραίων ~c_j~ και ~d_j\;(1 \le c_j,\;d_j \le n)~, τις ετικέτες των τελικών σημείων των μονοπατιών που απαιτείται να είναι πολύχρωμα. Οι κόμβοι ~c_i~ και ~d_i~ δεν είναι γειτονικοί.

Έξοδος

Στη μοναδική γραμμή εκτυπώστε τον αριθμό των τρόπων για να χρωματίσετε τις άκρες του δέντρου έτσι ώστε κάθε μία από τις ~m~ δοθείσες διαδρομές να είναι πολύχρωμη, modulo ~10^9 + 7~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~m = 1~
2	15	~m = 2~
3	10	Κάθε άκρη δέντρου ανήκει το πολύ σε ένα από τα ~m~ δοσμένα μονοπάτια.
4	10	~1 \le n \le 15,\;lk = 2~
5	65	Κανένας επιπλέον περιορισμός.

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

input

3 1 2
1 2
2 3
1 3

output

2

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

Το δέντρο αποτελείται μόνο από δύο κλαδιά, και τα δύο εκ των οποίων είναι μέρος μιας πολύχρωμης διαδρομής μεταξύ των κόμβων 1 και 3. Έτσι, τα δύο κλαδιά πρέπει να έχουν διαφορετικό χρώμα. Ένας τέτοιος χρωματισμός επιτυγχάνεται χρωματίζοντας το κλαδί 1-2 στο χρώμα 1, και το κλαδί 2-3 στο χρώμα 2, ενώ το άλλο λαμβάνεται με εναλλαγή αυτών των χρωμάτων έτσι ώστε το 1-2 να έχει χρώμα 2 και το 2-3 να έχει χρώμα 1.

input

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

output

0

input

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

output

6