#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("unroll-loops") //#pragma warning(disable : 4996) #ifdef _MSC_VER #include #define __builtin_popcount __popcnt #define __builtin_popcountll __popcnt64 #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPR(i, n) for (int i = n - 1; i >= 0; --i) #define FOR(i, m, n) for (int i = m; i < n; ++i) #define FORR(i, m, n) for (int i = m - 1; i >= n; --i) #define SORT(v, n) sort(v, v + n); #define VSORT(v) sort(v.begin(), v.end()); #define REVERSE(v, n) reverse(v, v + n); #define VREVERSE(v) reverse(v.begin(), v.end()) #define ll long long #define print(x) cout << (x) << '\n' #define pe(x) cout << (x) << " " #define DEBUG(x) cout << #x << ": " << x << endl #define lb(v, n) lower_bound(v.begin(), v.end(), (n)) #define ub(v, n) upper_bound(v.begin(), v.end(), (n)) #define int long long //#define double long double #define all(x) (x).begin(), (x).end() #define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ") template inline void chmin(T1& a, T2 b) { if (a > b) a = b; } template inline void chmax(T1& a, T2 b) { if (a < b) a = b; } typedef pair pii; typedef pair pll; typedef array arr3; std::random_device rd; std::mt19937 mt(rd()); constexpr ll MOD = 1e9+7; constexpr int MAX = 200020; const double pi = acos(-1); // constexpr double EPS = 1e-10; constexpr ll INF = 1e16; void yes(bool c) { if (c) print("Yes"); else print("No"); }; long long fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; } ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; } ll mult(ll x, ll y) { return (x * y) % MOD; } ll bin_pow(ll x, ll p) { if (p == 0) return 1; if (p & 1) return mult(x, bin_pow(x, p - 1)); return bin_pow(mult(x, x), p / 2); } template struct SegmentTree { int n; T unit; vectordat; function func; SegmentTree(const int N, T _unit, function _func) :unit(_unit), func(_func) { n = 1; //簡単のため、要素数を2のべき乗に while (n < N)n *= 2; dat.assign(2 * n, unit); } void update(int k, T a) { k += n - 1;//葉の節点 dat[k] = a; //上りながら更新 while (k > 0) { k = (k - 1) / 2; dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]); } } T _query(int a, int b, int k, int l, int r) { //[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す if (r <= a || b <= l)return unit; //[a,b)が[l,r)を完全に含んでいれば、この節点の値 if (a <= l && r <= b)return dat[k]; else { int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2); int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r); return func(vl, vr); } } //[a,b) T query(int a, int b) { return _query(a, b, 0, 0, n); } }; //auto f = [](int a, int b) {return a + b; }; //SegmentTreeseg(N,0,f); long long gcd(long long x, long long y) { long long m = max(x, y), n = min(x, y); if (n == 0)return m; if (m%n == 0)return n; else return gcd(m%n, n); } const int mod = 1000000007; //const int mod = 998244353; struct mint { ll x; // typedef long long ll; mint(ll x = 0) :x((x%mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { return mint(*this) += a; } mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod - 2); } mint& operator/=(const mint a) { return *this *= a.inv(); } mint operator/(const mint a) const { return mint(*this) /= a; } }; istream& operator>>(istream& is, const mint& a) { return is >> a.x; } ostream& operator<<(ostream& os, const mint& a) { return os << a.x; } /* mint dp[l][r][k]:=[l,r)でR-B=kとする場合の数→むり~ mint dp[i][k]:=左からi文字目まででR-B=kとする場合の数 */ //{ // cin >> S; // cin >> K; // dp[0][3000] = 1; // int N = S.size(); // stackstk; // int idx = 0; // int M = 0; // REP(i, N) { // if (S[i] == '(') { // stk.push(i); // idx++; // } // else { // int now = stk.top(); // stk.pop(); // if (!stk.empty()) { // int par = stk.top(); // G[par].push_back(now); // } // } // } // dfs(0, 0); //} vectorG[2020]; int siz[2020]; int dfs(int n, int pre) { int res = 1; for (auto nxt : G[n]) { if (nxt == pre)continue; res += dfs(nxt, n); } return siz[n] = res; } int N, K; mint dp[2020][2020];//頂点iの部分木のうちj個を黒く塗る場合の数 void rec(int n, int pre) { //cerr << "n:" << n << endl; for (auto nxt : G[n]) { if (nxt == pre)continue; rec(nxt, n); } int sum = 1; dp[n][0] = 1; for (auto nxt : G[n]) { if (nxt == pre)continue; vectortmp(2020); REP(i, sum + 1) { REP(j, siz[nxt] + 1) { if (i + j > K)break; tmp[i + j] += dp[n][i] * dp[nxt][j]; } } sum += siz[nxt]; REP(i, sum + 1)dp[n][i] = tmp[i]; } dp[n][siz[n]] = dp[n][siz[n] - 1]; } void solve() { cin >> N >> K; REP(i, N - 1) { int u, v; cin >> u >> v; //u--, v--; G[u].push_back(v); G[v].push_back(u); } dfs(0, 0); rec(0, 0); print(dp[0][K]); } signed main() { cin.tie(0); ios::sync_with_stdio(false); // int q; // cin >> q; // while (q--) solve(); }