#include #include using mint = atcoder::modint1000000007; using namespace std; using ll = long long; mint ans; int k0; struct Graph { struct Sub { Sub() : x(k0, 1) {} Sub &operator+=(const Sub &s) { for (int k = 0; k < k0; k++) { x[k] *= s.x[k]; } return *this; } Sub &add_root() { for (int k = 1; k < k0; k++) { x[k] += x[k - 1]; } return *this; } vector x; }; struct Vertex { int n; Sub s; }; struct Edge { int i, n, r; Sub s; }; Graph(int n, int m) : v(n, { -1, {} }), e(m), r(m), n(n), m(0) {} void add_edge(int i, int j) { e[m] = { j, v[i].n, 0, {} }; v[i].n = m; m++; } Sub dfs0(int i, int p) { Sub s; for (int j = v[i].n; j >= 0; j = e[j].n) { Edge& o = e[j]; if (o.i == p) continue; s += o.s = dfs0(o.i, i); } return s.add_root(); } void dfs1(int i, int p, Sub *r, Sub s0) { int l = 0; for (int j = v[i].n; j >= 0; j = e[j].n) { Edge& o = e[j]; if (o.i == p) o.s = s0; r[l++] = o.s; } for (int k = l - 1; k > 0; k--) { r[k - 1] += r[k]; } v[i].s = r[0].add_root(); Sub s; int k = 0; for (int j = v[i].n; j >= 0; j = e[j].n) { Edge& o = e[j]; k++; if (o.i != p) { Sub t = s; if (k < l) t += r[k]; dfs1(o.i, i, r + l, t.add_root()); } s += o.s; } } void solve() { dfs0(0, -1); dfs1(0, -1, &r[0], {}); ans = 0; dfs(0, -1); cout << ans.val() << endl; } void dfs(int i, int p) { Sub s, t; for (int j = v[i].n; j >= 0; j = e[j].n) { Edge& o = e[j]; if (o.i == p) { t = o.s; continue; } s += o.s; dfs(o.i, i); } if (p >= 0) { for (int k = 1; k < k0; k++) { ans += s.x[k] * t.x[k - 1]; } } else { for (int k = 0; k < k0; k++) { ans += s.x[k]; } } } vector v; vector e; vector r; int n, m; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n >> k0; Graph g(n, (n - 1) * 2); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; g.add_edge(a, b); g.add_edge(b, a); } g.solve(); return 0; }