Vladislav and a Great Legend

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;
}