Sereja and Tree 2

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has a rooted tree of N nodes with node 1 being the root node. He wants to find the number of ways of assigning an integer in the range [1, M] to each node, such that value of each node should be a multiple of it's parent node's value (for vertex #1 there is no parent so any number fit condition). As the answer could be large, report it modulo (10^{9} + 7).
Input
The first line of input contains an integer T — the number of test cases. T tests follow.
First line of each test case contains two spaceseparated integers N and M. Each of the next N1 lines contains two integers (u, v) — a pair of vertices connected by an edge.
Output
For each test case, output a single integer corresponding to the answer in separate line.Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 500
 1 ≤ M ≤ 20000
 1 ≤ u, v ≤ N
 It is guaranteed that the given graph is a tree (i.e., there won't be any cycles or selfloops).
Example
Input: 2 3 2 1 2 1 3 1 100 Output: 5 100
Explanation
In first test case there are five possible assigns of numbers: [1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 2, 2]. In second test case there are hundred possible assigns: [1], [2], [3], ..., [100].Author:  sereja 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/SEATR2 
Tags  cook64, dynamicprogramming, maths, medium, sereja, tree 
Date Added:  9112015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 