Tree Traversals

Ο Yevin Kang έχει ένα δέντρο με ~N~ κορυφές, αριθμημένες από το ~1~ έως το ~N~. Ένα δέντρο είναι ένας μη κατευθυνόμενος, συνεκτικός γράφος που δεν περιέχει κύκλους.

Έστω ~K~ ένας θετικός ακέραιος. Ορίζουμε τη συνάρτηση ~f(K)~ ως εξής.

Για οποιεσδήποτε δύο κορυφές ~1 \le u,v \le N~, έστω ~d(u,v)~ ο αριθμός των ακμών στο απλό μονοπάτι που συνδέει την κορυφή ~u~ με την κορυφή ~v~. Ειδικότερα, ~d(u,u)=0~ για κάθε ~1 \le u \le N~.

Μια μετάθεση ~p_1,\ldots,p_N~ των αριθμών ~1,\ldots,N~ είναι καλή αν ικανοποιεί όλες τις ακόλουθες συνθήκες:

• ~d(p_{i-1},p_i) \le K~ για όλα τα ~i=2,\ldots,N~.
• ~d(1,p_i) \le d(1,p_j)~ για όλα τα ζεύγη ακεραίων ~(i,j)~ με ~1 \le i < j \le N~.

Τότε, η ~f(K)~ είναι το πλήθος των καλών μεταθέσεων.

Ο Yevin θεωρεί ότι αυτό το πρόβλημα είναι πολύ εύκολο, γι' αυτό σου δίνει ~Q~ θετικούς ακέραιους ~K_1,\ldots,K_Q~. Σου ζητά να εκτυπώσεις τις τιμές ~f(K_1),f(K_2),\ldots,f(K_Q)~, modulo ~10^9+7~.

Μπορεί επίσης να είναι χρήσιμο να σημειωθεί ότι το «mod» αντιστοιχεί στον τελεστή % στις περισσότερες γλώσσες προγραμματισμού και δηλώνει το υπόλοιπο της διαίρεσης. Για παράδειγμα, ~5 \bmod 3=2~ και ~17 \bmod 4=1~.

Είσοδος

Κάθε αρχείο περιέχει πολλαπλά αρχεία ελέγχου.

Η πρώτη γραμμή κάθε αρχείου θα περιέχει έναν ακέραιο ~T~ (~1 \le T \le 5 \times 10^5~) - το πλήθος των αρχείων ελέγχου.

Η πρώτη γραμμή κάθε αρχείου ελέγχου θα περιέχει δύο ακεραίους ~N,Q~, χωρισμένους με κενό (~1 \le Q \le N \le 5 \times 10^5~).

Καθεμία από τις επόμενες ~N-1~ γραμμές περιέχει δύο ακεραίους ~u,v~, χωρισμένους με κενό, που δηλώνουν ότι υπάρχει μια ακμή που συνδέει τις κορυφές ~u~ και ~v~. Εγγυάται ότι οι ~N-1~ ακμές σχηματίζουν ένα δέντρο.

Η επόμενη γραμμή θα περιέχει ~Q~ ακεραίους ~K_1,\ldots,K_Q~, που αντιστοιχούν στα ερωτήματα.

Είναι εγγυημένο ότι το άθροισμα των ~N~ σε όλα τα αρχεία ελέγχου μιας δοκιμής, το οποίο συμβολίζεται με ~\sum N~, δεν υπερβαίνει το ~5 \times 10^5~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια στο ~\sum N~	Όρια στο ~Q~	Όρια στα ~K_i~
~2~	~1 \le \sum N \le 10~	~1 \le Q \le N~	~1 \le K_i \le N~
~3~	~1 \le \sum N \le 5 \times 10^5~	~1 \le Q \le \min(2,N)~	~1 \le K_i \le \min(2,N)~
~5~	~1 \le \sum N \le 3000~	~1 \le Q \le \min(5,N)~	~1 \le K_i \le N~
~7~	~1 \le \sum N \le 5 \times 10^5~	~1 \le Q \le \min(5,N)~	~1 \le K_i \le N~
~8~	~1 \le \sum N \le 5 \times 10^5~	~1 \le Q \le N~	~1 \le K_i \le N~

Έξοδος

Για κάθε test case, εκτυπώστε μία γραμμή με ~Q~ ακεραίους χωρισμένους με κενά - τις τιμές ~f(K_1),\ f(K_2),\ ...,\ f(K_Q)~, modulo ~10^9+7~.

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

input

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

output

0 2 2
0 6 12

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

Τα δύο δέντρα της εισόδου του παραδείγματος φαίνονται παρακάτω.

  1
 / \
2   3

    1
   / \
  2   3
     /|\
    4 5 6

Στο πρώτο test case, για ~K=2~ ή ~K=3~, τόσο η μετάθεση ~[1,2,3]~ όσο και η μετάθεση ~[1,3,2]~ είναι καλές.

Η μετάθεση ~[2,1,3]~ δεν είναι καλή για καμία τιμή του ~K~, επειδή η συνθήκη ~d(1,p_1) \le d(1,p_2)~ παραβιάζεται:

~d(1,p_1)=1 \not\le 0=d(1,p_2)~.

Μπορεί να αποδειχθεί ότι δεν υπάρχει καλή μετάθεση για ~K=1~.

Στο δεύτερο test case, η μετάθεση ~[1,3,2,4,5,6]~ είναι καλή για ~K=3~, αλλά δεν είναι καλή για ~K=2~, επειδή ~d(2,4)=3 \not\le 2~.