#include #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 = 0; k <= size[v]; k++) { for (int subk = 0; subk <= size[to]; subk++) { if (k == size[v] and subk == size[to]) continue; (values[k + subk] += dp[v][k] * dp[to][subk]) %= MOD; } } // valuesをdpに移す size[v] += size[to]; copy(values, values + (K + 1), dp[v]); } 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; }