Usmjeri

Μας δίνεται ένα δέντρο¹ με τους ~N~ κόμβους να συμβολίζονται με διαφορετικούς θετικούς ακέραιους από το 1 έως το ~N~. Επιπλέον, μας δίνονται ~M~ ζεύγη κόμβων από το δέντρο με τη μορφή ~(a_1,\;b_1),\;(a_2,\;b_2),\;\ldots,\;(a_M,\;b_M)~.
Πρέπει να κατευθύνουμε κάθε ακμή του δέντρου έτσι ώστε για κάθε δεδομένο ζεύγος κόμβων ~(a_i,\;b_i)~ να υπάρχει μια διαδρομή από το ~a_i~ στο ~b_i~ ή από το ~b_i~ έως το ~a_i~. Πόσοι διαφορετικοί τρόποι υπάρχουν για να το πετύχετε αυτό;
Εφόσον η λύση μπορεί να είναι αρκετά μεγάλη, προσδιορίστε την στη μορφή υπολοίπου ακέραιας διαίρεσης με το ~10^9 + 7~ (modulo ~10^9 + 7~).

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους αριθμούς ~N~ και ~M\;(1 \le N, M \le 3 \cdot 10^5)~, τον αριθμό των κόμβων στο δέντρο και τον αριθμό των δεδομένων ζευγών κόμβων, αντίστοιχα.
Κάθε μία από τις ακόλουθες ~N - 1~ γραμμές περιέχει δύο θετικούς ακέραιους αριθμούς, με τις ετικέτες των κόμβων να συνδέονται με μια ακμή.
Η ~i~-οστή από τις ακόλουθες ~M~ γραμμές περιέχει δύο διαφορετικούς θετικούς ακέραιους αριθμούς ~a_i~ και ~b_i~, τις ετικέτες των κόμβων από το ~i~-οστό ζεύγος κόμβων. Τα ζεύγη κόμβων θα είναι αμοιβαία διαφορετικά.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 20% των συνολικών πόντων, το δεδομένο δέντρο θα είναι μια αλυσίδα. Με άλλα λόγια, ο κόμβος ~i~ θα συνδεθεί με ένα άκρο στον κόμβο ~i + 1~ για κάθε ~i < N~.
Σε πρόσθετες περιπτώσεις δοκιμών αξίας 40% των συνολικών πόντων, θα ισχύει ~N, M \le 5 \times 10^3~.

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

input

4 1
1 2
2 3
3 4
2 4

output

4

input

7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6

output

8

input

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

output

0

Ένα δέντρο είναι ένα γράφημα που αποτελείται από ~N~ κόμβους και ~N - 1~ ακμές τέτοιες ώστε να υπάρχει μια διαδρομή από κάθε κόμβο σε έναν άλλο κόμβο.