#include #include using namespace std; using int64 = long long; const int64 MOD = 1e9 + 7; vector T[2010]; int64 dp[2010][2010]; int size[2010]; int N, K; int64 dfs(int v, int par) { size[v] = 1; dp[v][0] = 1; for (int to : T[v]) { if (to == par) continue; dfs(to, v); int64 values[2010] = {}; for (int k = min(K, size[v] - 1); k >= 0; k--) { for (int subk = 0; subk + k <= min(size[v] + size[to] - 1, K) and subk <= size[to]; subk++) { (values[k + subk] += dp[v][k] * dp[to][subk]) %= MOD; } } // valuesをdpに移す size[v] += size[to]; for (int k = 0; k <= min(K, size[v]); k++) for (int st = 0; st <= 1; st++) dp[v][k] = values[k]; } dp[v][size[v]] = 1; return dp[v][K]; } int main() { cin >> N >> K; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; T[a].push_back(b); T[b].push_back(a); } cout << dfs(0, -1) << endl; return 0; }