Ptree

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

We define a tree with positive integer weight on node as Ptree, when product of each pair of neighbor nodes's weight is not large than P. On the tree, if there is exactly one edge between two nodes x and y, then we call x and y a pair of neighbor nodes.
Now you are given integer P and a tree with N nodes(rank them from 1 to N), I wonder how many way to assign the nodes weight so that to construct a Ptree.

Input

The first line contains two integers N and P.(1 <= N <= 1,000, 1 <= P <= 1,000,000)
The Next N - 1 lines each line contains two integers x and y, indicating there is an edge between node x and node y.

Output

Output the answer moduled 1,000,000,007(1e9+7)。

Sample Input

3 4
1 2
1 3

Sample Output

22

Source

dut200901102

Manager

Information
Solved Number23
Submit Number98
Problem Tags
dp
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel