Description
A tree is an undirected connected graph without cycles.
You are given a tree of n vertices. Find the number of ways to choose exactly k vertices in this tree (i. e. a k-element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer c such that for all u,v (u≠v, u,v are in selected vertices) du,v=c, where du,v is the distance from u to v).
Since the answer may be very large, you need to output it modulo 109+7.
Input
The first line contains one integer t (1≤t≤10) — the number of test cases. Then t 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 n and k (2≤k≤n≤100) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then n−1 lines follow, each of them contains two integers u and v (1≤u,v≤n, u≠v) 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 k vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo 109+7 (in other words, print the remainder when divided by 1000000007).
Example
input
3 4 2 1 2 2 3 2 4 3 3 1 2 2 3 5 3 1 2 2 3 2 4 4 5
output
6 0 1
typedef int itn; struct node{ int v,nex; }e[107 << 1]; int head[107 << 1],cnt; int n,k; void init(){ cnt = 0; for(int i=0;i<(107<<1);i++) head[i] = -1; } void add(int u,int v){ e[cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt ++; } int siz[107]; bool vis[107]; int dp[107][107]; void dfs(int u,int fa,int dep,int pnt){ vis[u] = 1; if(dep == pnt){ siz[u] ++; return; } for(int i=head[u];~i;i=e[i].nex){ int to = e[i].v; if(to == fa) continue; dfs(to,u,dep+1,pnt); siz[u] += siz[to]; } } int main() { int _ = read; while(_ --){ n = read,k = read; init(); for(int i=1;i<n;i++){ int u = read,v = read; add(u,v); add(v,u); } ll ans = 0; if(k == 2){ ans = n * (n - 1) / 2 % mod; printf("%lld\n",ans); continue; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ memset(vis,0,sizeof vis); memset(siz,0,sizeof siz); memset(dp,0,sizeof dp); dfs(i,0,0,j); dp[0][0] = 1; int it = 0; for(int tj = head[i];~tj;tj=e[tj].nex){ int to = e[tj].v; if(siz[to] == 0) continue; for(int kk=0;kk<=it;kk++){ dp[it+1][kk] += dp[it][kk]; dp[it+1][kk] %= mod; dp[it+1][kk+1] += dp[it][kk] * siz[to] % mod; dp[it+1][kk+1] %= mod; } it ++; } ans += dp[it][k]; ans %= mod; } } printf("%lld\n",ans); } return 0; }
