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 (109 + 7).
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 space-separated integers N and M. Each of the next N-1 lines contains two integers (u, v) — a pair of vertices connected by an edge.
OutputFor each test case, output a single integer corresponding to the answer in separate line.
- 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 self-loops).
Input: 2 3 2 1 2 1 3 1 100 Output: 5 100
ExplanationIn 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: , , , ..., .
|Tags||cook64, dynamic-programming, maths, medium, sereja, tree|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.