#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define mod 1000000007 using namespace std; typedef pair P; llint n, k; vector G[1005]; typedef pair P; int parent[1005]; llint dp[1005][1005], dp2[1005][1005]; llint sum[1005][1005], sum2[1005][1005]; llint get(int u, int v, int x) { if(parent[u] == v) return dp2[u][x]; else return dp[v][x]; } llint getsum(int u, int v, int x) { if(parent[u] == v) return sum2[u][x]; else return sum[v][x]; } void dfs(int v, int p) { parent[v] = p; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; dfs(G[v][i], v); } for(int j = 1; j <= k; j++){ llint mul = 1; for(int i = 0; i < G[v].size(); i++){ int u = G[v][i]; if(u == p) continue; mul *= getsum(v, u, j), mul %= mod; } dp[v][j] = mul; sum[v][j] = sum[v][j-1] + dp[v][j], sum[v][j] %= mod; } } llint lsum[1005], rsum[1005]; void dfs2(int v, int p) { llint m = G[v].size(), mul; for(int j = 1; j <= k; j++){ mul = lsum[0] = 1; for(int i = 0; i < m; i++){ int u = G[v][i]; mul *= getsum(v, u, j), mul %= mod; // lsum[i+1] = mul; } mul = rsum[m+1] = 1; for(int i = m-1; i >= 0; i--){ int u = G[v][i]; mul *= getsum(v, u, j), mul %= mod; // rsum[i+1] = mul; } for(int i = 0; i < m; i++){ int u = G[v][i]; if(u == p) continue; dp2[u][j] = lsum[i] * rsum[i+2] % mod; sum2[u][j] = (sum2[u][j-1] + dp2[u][j]) % mod; } } for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; dfs2(G[v][i], v); } } int size[1005]; bool used[1005]; int sizedfs(int v, int pre) { int ret = 1; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == pre) continue; if(used[G[v][i]]) continue; ret += sizedfs(G[v][i], v); } return size[v] = ret; } int centdfs(int v, int pre, int sz) { for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == pre) continue; if(used[G[v][i]]) continue; if(size[G[v][i]] > sz/2) return centdfs(G[v][i], v, sz); } return v; } llint calcdfs(llint v, llint p, llint k) { llint ret = 0; if(p != -1) ret = getsum(p, v, k-1); llint mul = 1; for(int i = 0; i < G[v].size(); i++){ llint u = G[v][i]; if(u == p) continue; if(used[u]){ mul *= getsum(v, u, k-1), mul %= mod; continue; } mul *= calcdfs(G[v][i], v, k), mul %= mod; } ret += mul, ret %= mod; return ret; } llint ans = 0; void solve(int v) { sizedfs(v, -1); v = centdfs(v, -1, size[v]); /* 処理 */ for(int i = 2; i <= k; i++){ ans += calcdfs(v, -1, i); ans %= mod; } used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(used[G[v][i]]) continue; solve(G[v][i]); } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; llint u, v; for(int i = 1; i <= n-1; i++){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } if(k == 1){ cout << 1 << endl; return 0; } dfs(1, -1); dfs2(1, -1); /*for(int i = 1; i <= n; i++){ for(int j = 0; j < G[i].size(); j++){ cout << i << " " << G[i][j] << " : "; for(int l = 1; l <= k; l++){ cout << get(i, G[i][j], l) << " "; } cout << endl; } }*/ solve(1); ans += 1, ans %= mod; cout << ans << endl; return 0; }