#include #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; lli mod = 1e9 + 7; vector e[2005]; lli dp[2005][2005] = {}; lli memo[2005] = {}; int n, k; // iの部分木でj個色が塗られている場合の数 int dfs(int cur, int par) { if (cur != 0 and e[cur].size() == 1) { // leaf dp[cur][1] = 1; dp[cur][0] = 1; memo[cur] = 1; return 1; } int size = 1; for (auto s : e[cur]) { if (s == par) continue; size += dfs(s, cur); } dp[cur][0] = 1; for (auto s : e[cur]) { if (s == par) continue; vector tmp(n + 1, 0); rep(i, n + 1) { tmp[i] = dp[cur][i]; } vector hoge(n + 1, 0); rep(i, memo[s] + 1) { rep(j, n + 1) { if (i + j > n) continue; hoge[i + j] += (tmp[j] % mod * dp[s][i]) % mod; hoge[i + j] %= mod; } } rep(i, n + 1) dp[cur][i] = hoge[i]; } dp[cur][size] = 1; memo[cur] = size; return size; } int main() { cin >> n >> k; int a, b; rep(i, n - 1) { cin >> a >> b; e[a].push_back(b); e[b].push_back(a); } dfs(0, -1); cout << dp[0][k] << endl; }