#P1551F. Equidistant Vertices
Equidistant Vertices
Description
A tree is an undirected connected graph without cycles.
You are given a tree of vertices. Find the number of ways to choose exactly vertices in this tree (i. e. a -element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer such that for all (, are in selected vertices) , where is the distance from to ).
Since the answer may be very large, you need to output it modulo .
The first line contains one integer () — the number of test cases. Then test cases follow.
Each test case is preceded by an empty line.
Each test case consists of several lines. The first line of the test case contains two integers and () — the number of vertices in the tree and the number of vertices to be selected, respectively. Then lines follow, each of them contains two integers and (, ) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.
For each test case output in a separate line a single integer — the number of ways to select exactly vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo (in other words, print the remainder when divided by ).
Input
The first line contains one integer () — the number of test cases. Then test cases follow.
Each test case is preceded by an empty line.
Each test case consists of several lines. The first line of the test case contains two integers and () — the number of vertices in the tree and the number of vertices to be selected, respectively. Then lines follow, each of them contains two integers and (, ) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.
Output
For each test case output in a separate line a single integer — the number of ways to select exactly vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo (in other words, print the remainder when divided by ).