#include using namespace std; #define int long long const int MOD = 1000000007; vector > g; vector > > dp; vector > prod; void extgcd(int a, int b, int& x, int& y) { if (b != 0) { extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } } int mod_inverse(int a, int p) { int x, y; extgcd(a, p, x, y); return (p + x % p) % p; } void add(int& a, const int& b) { a += b; if (a >= MOD) a -= MOD; } int N, K; vector P; void dfs1(int a, int p) { for (int i = 0; i < g[a].size(); i++) { if (g[a][i] != p) { dfs1(g[a][i], a); for (int k = 0; k < K; k++) { dp[a][i][k] = prod[g[a][i]][k]; } for (int k = 1; k < K; k++) { add(dp[a][i][k], dp[a][i][k - 1]); } for (int k = 0; k < K; k++) { prod[a][k] = (prod[a][k] * dp[a][i][k]) % MOD; } } } } void dfs2(int a, int p, int x) { for (int i = 0; i < g[a].size(); i++) { if (g[a][i] != p) { dfs2(g[a][i], a, i); } else { P[a] = i; for (int k = 0; k < K; k++) { dp[a][i][k] = prod[p][k] * mod_inverse(dp[p][x][k], MOD) % MOD; } for (int k = 1; k < K; k++) { add(dp[a][i][k], dp[a][i][k - 1]); } for (int k = 0; k < K; k++) { prod[a][k] = (prod[a][k] * dp[a][i][k]) % MOD; } } } } signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; P.resize(N, -1); g.resize(N); dp.resize(N); prod.resize(N, vector(K, 1)); int res = 0; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } for (int i = 0; i < N; i++) { dp[i].resize(g[i].size(), vector(K, 0)); } dfs1(0, -1); dfs2(0, -1, -1); // for (int i = 0; i < N; i++) { // for (int j = 0; j < g[i].size(); j++) { // cerr << i << "->" << g[i][j] << endl; // for (int k = 0; k < K; k++) { // cerr << dp[i][j][k] << " "; // } // cerr << endl; // } // } for (int i = 0; i < N; i++) { for (int j = 0; j < g[i].size(); j++) { if (j != P[i]) { int b = g[i][j]; assert(g[b][P[b]] == i); for (int k = 1; k < K; k++) { add(res, ((dp[i][j][k] - dp[i][j][k - 1]) * dp[b][P[b]][k - 1]) % MOD); } } } } for (int k = 0; k < K; k++) { add(res, prod[0][k]); } add(res, MOD); add(res, MOD); add(res, MOD); cout << res << endl; }