#include #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef tuple t3; typedef tuple t4; typedef tuple t5; #define rep(a,n) for(ll a = 0;a < n;a++) template static inline void chmin(T& ref, const T value) { if (ref > value) ref = value; } template static inline void chmax(T& ref, const T value) { if (ref < value) ref = value; } #include using namespace atcoder; typedef modint1000000007 mint; int main() { int n, k; cin >> n >> k; vector> g(n); rep(i, n - 1) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } vector cs(n, 0); function dfs = [&](int current, int parent) { int c = 1; for (auto x : g[current]) { if (x == parent) continue; c += dfs(x, current); } cs[current] = c; return c; }; dfs(0, -1); vector dp2(k + 1, 0); dp2[k] = 1; function&)> dfs2 = [&](int current, int parent, vector& dp) { //塗らないパターン vector temp = dp; //子供を個別に塗り分けていくパターン for (auto x : g[current]) { if (x == parent) continue; dfs2(x, current, temp); } //自分以下をすべて塗るパターン for (int x = cs[current]; x <= k; x++) { temp[x - cs[current]] += dp[x]; } dp = temp; }; dfs2(0, -1, dp2); cout << dp2[0].val() << endl; return 0; }