A great legend used to be here, but some troll hacked Codeforces and erased it. Too bad for us, but in the troll society he earned a title of an ultimate-greatest-over troll. At least for them, it’s something good. And maybe a formal statement will be even better for us?
You are given a tree $T$ with $n$ vertices numbered from $1$ to $n$. For every non-empty subset $X$ of vertices of $T$, let $f(X)$ be the minimum number of edges in the smallest connected subtree of $T$ which contains every vertex from $X$.
You’re also given an integer $k$. You need to compute the sum of $(f(X))^k$ among all non-empty subsets of vertices, that is:
$$ \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. $$
As the result might be very large, output it modulo $10^9 + 7$.
Input
The first line contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $1 \leq k \leq 200$) — the size of the tree and the exponent in the sum above.
Each of the following $n – 1$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq n$) — the indices of the vertices connected by the corresponding edge.
It is guaranteed, that the edges form a tree.
Output
Print a single integer — the requested sum modulo $10^9 + 7$.
Examples
input
4 1 1 2 2 3 2 4
output
21
input
4 2 1 2 2 3 2 4
output
45
input
5 3 1 2 2 3 3 4 4 5
output
780
Note
In the first two examples, the values of $f$ are as follows:
$f(\{1\}) = 0$
$f(\{2\}) = 0$
$f(\{1, 2\}) = 1$
$f(\{3\}) = 0$
$f(\{1, 3\}) = 2$
$f(\{2, 3\}) = 1$
$f(\{1, 2, 3\}) = 2$
$f(\{4\}) = 0$
$f(\{1, 4\}) = 2$
$f(\{2, 4\}) = 1$
$f(\{1, 2, 4\}) = 2$
$f(\{3, 4\}) = 2$
$f(\{1, 3, 4\}) = 3$
$f(\{2, 3, 4\}) = 2$
$f(\{1, 2, 3, 4\}) = 3$
Solution:
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template <typename T> class Modular { public: using Type = typename decay<decltype(T::value)>::type; constexpr Modular() : value() {} template <typename U> Modular(const U& x) { value = normalize(x); } template <typename U> static Type normalize(const U& x) { Type v; if (-mod() <= x && x < mod()) v = static_cast<Type>(x); else v = static_cast<Type>(x % mod()); if (v < 0) v += mod(); return v; } const Type& operator()() const { return value; } template <typename U> explicit operator U() const { return static_cast<U>(value); } constexpr static Type mod() { return T::value; } Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; } Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; } template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); } template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); } Modular& operator++() { return *this += 1; } Modular& operator--() { return *this -= 1; } Modular operator++(int) { Modular result(*this); *this += 1; return result; } Modular operator--(int) { Modular result(*this); *this -= 1; return result; } Modular operator-() { return Modular(-value); } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) { value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value)); return *this; } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) { int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod()); value = normalize(value * rhs.value - q * mod()); return *this; } template <typename U = T> typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) { value = normalize(value * rhs.value); return *this; } Modular inverse() const { Type a = value, b = mod(), u = 0, v = 1; while (a != 0) { Type t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); return Modular(u); } Modular& operator/=(const Modular& other) { return *this *= other.inverse(); } template <typename U> friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs); template <typename U> friend std::istream& operator>>(std::istream& stream, Modular<U>& number); private: Type value; }; template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; } template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); } template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; } template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template<typename T, typename U> Modular<T> power(const Modular<T>& a, const U& b) { assert(b >= 0); Modular<T> x = a, res = 1; U p = b; while (p > 0) { if (p & 1) res *= x; x *= x; p >>= 1; } return res; } template <typename T> string to_string(const Modular<T>& number) { return to_string(number()); } template <typename T> std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) { return stream << number(); } template <typename T> std::istream& operator>>(std::istream& stream, Modular<T>& number) { stream >> number.value; number.value = Modular<T>::normalize(number.value); return stream; } struct VarMod { static int value; }; int VarMod::value; //using Mint = Modular<VarMod>; using Mint = Modular<std::integral_constant<int, (int) 1e9 + 7>>; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } vector<vector<Mint>> dp1(n, vector<Mint>(k + 1, 0)); vector<vector<Mint>> dp2(n, vector<Mint>(k + 1, 0)); vector<vector<Mint>> dp3(n, vector<Mint>(k + 1, 0)); vector<Mint> aux1(k + 1); vector<Mint> aux2(k + 1); vector<Mint> aux3(k + 1); vector<int> sz(n); function<void(int, int)> dfs = [&](int v, int pr) { dp1[v][0] = 0; dp2[v][0] = 2; dp3[v][0] = 1; sz[v] = 1; for (int u : g[v]) { if (u == pr) { continue; } dfs(u, v); int bound = min(sz[v] - 1 + sz[u], k); for (int i = 0; i <= bound; i++) { aux1[i] = aux2[i] = aux3[i] = 0; } for (int i = 0; i <= min(sz[v] - 1, k); i++) { for (int j = 0; j <= min(sz[u], k - i); j++) { aux3[i + j] += dp3[v][i] * dp3[u][j]; aux2[i + j] += dp2[v][i] * dp2[u][j]; aux1[i + j] += dp1[v][i] * dp3[u][j]; aux1[i + j] += dp3[v][i] * dp1[u][j]; } } for (int i = 0; i <= bound; i++) { dp1[v][i] = aux1[i]; dp2[v][i] = aux2[i]; dp3[v][i] = aux3[i]; } sz[v] += sz[u]; } if (v != 0) { for (int j = min(k, sz[v]) - 1; j >= 0; j--) { dp3[v][j + 1] += dp3[v][j]; dp1[v][j + 1] += dp1[v][j]; dp1[v][j + 1] += dp2[v][j]; dp2[v][j + 1] += dp3[v][j]; } } }; dfs(0, -1); const int MAX = max(n, k); vector<Mint> fact(MAX + 1); fact[0] = 1; for (int i = 0; i < MAX; i++) { fact[i + 1] = fact[i] * (i + 1); } vector<Mint> inv_fact(MAX + 1); for (int i = 0; i <= MAX; i++) { inv_fact[i] = 1 / fact[i]; } auto C = [&](int n, int k) { if (k < 0 || k > n) return Mint(0); return fact[n] * inv_fact[k] * inv_fact[n - k]; }; vector<Mint> v(k + 1); for (int i = 0; i <= k; i++) { v[i] = dp1[0][i] + dp2[0][i] - (i + 1) * dp3[0][i]; } vector<Mint> w(k + 1); for (int i = 0; i <= k; i++) { for (int j = 0; j <= i; j++) { w[i] += v[j] * C(n - 1 - j, i - j) * (j % 2 == 1 ? -1 : 1); } } vector<vector<Mint>> stir(k + 1, vector<Mint>(k + 1, 0)); stir[0][0] = 1; for (int i = 0; i < k; i++) { for (int j = 0; j <= i; j++) { stir[i + 1][j] += stir[i][j] * j; stir[i + 1][j + 1] += stir[i][j]; } } Mint ans = 0; for (int i = 1; i <= k; i++) { ans += w[i] * stir[k][i] * fact[i]; } cout << ans << '\n'; return 0; }