Problem: You are given a tree of n vertices. You are to select k (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not contained in any path, edges that are a part of exactly one of these paths, and edges that are parts of all selected paths, and the latter set should be non-empty.

Compute the number of ways to select k paths modulo 998244353.

The paths are enumerated, in other words, two ways are considered distinct if there are such i (1 ≤ i ≤ k) and an edge that the i-th path contains the edge in one way and does not contain it in the other.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 10^{5}) — the number of vertices in the tree and the desired number of paths.

The next n - 1 lines describe edges of the tree. Each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — the endpoints of an edge. It is guaranteed that the given edges form a tree.

Output

Print the number of ways to select k enumerated not necessarily distinct simple paths in such a way that for each edge either it is not contained in any path, or it is contained in exactly one path, or it is contained in all k paths, and the intersection of all paths is non-empty. 

As the answer can be large, print it modulo 998244353.

Examples

Input

3 2
1 2
2 3


Output

7


Input

5 1
4 1
2 3
4 5
2 1


Output

10


Input

29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29


Output

125580756

Note

In the first example the following ways are valid：

  * ((1,2), (1,2)), 
  * ((1,2), (1,3)), 
  * ((1,3), (1,2)), 
  * ((1,3), (1,3)), 
  * ((1,3), (2,3)), 
  * ((2,3), (1,3)), 
  * ((2,3), (2,3)). 



In the second example k=1, so all n ⋅ (n - 1) / 2 = 5 ⋅ 4 / 2 = 10 paths are valid.

In the third example, the answer is ≥ 998244353, so it was taken modulo 998244353, don't forget it!

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
using namespace std;
const int P = 998244353;
const int G = 3;
const int Gi = (P + 1) / G;
inline long long Add(long long a, long long b) {
  a += b;
  if (a >= P) a -= P;
  return a;
}
inline void ADD(long long &a, long long b) {
  a += b;
  if (a >= P) a -= P;
}
int n, K;
long long jie[101000], jieni[101000];
inline long long get_c(int n, int m) {
  if (n < 0 || m < 0 || (n - m) < 0) return 0;
  return jie[n] * jieni[m] % P * jieni[n - m] % P;
}
struct edge {
  int nxt, to;
} e[101000 << 1];
int head[101000], ecnt;
inline void addedge(int from, int to) {
  e[++ecnt] = (edge){head[from], to};
  head[from] = ecnt;
}
inline long long quickpow(long long x, int k) {
  long long res = 1;
  while (k) {
    if (k & 1) res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
inline void init() {
  jie[0] = jieni[0] = 1;
  int up = max(n, K) + 10;
  for (int i = 1; i <= up; ++i) jie[i] = jie[i - 1] * i % P;
  jieni[up] = quickpow(jie[up], P - 2);
  for (int i = up - 1; i; --i) jieni[i] = jieni[i + 1] * (i + 1) % P;
}
long long A[101000 << 2], B[101000 << 2];
int r[101000 << 2], limi;
namespace jzpntt {
inline void ntt(long long *a, int type) {
  for (int i = 0; i < limi; ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < limi; i <<= 1) {
    long long T = quickpow(type == 1 ? G : Gi, (P - 1) / (i << 1));
    for (int j = 0; j < limi; j += (i << 1)) {
      long long t = 1;
      for (int k = 0; k < i; ++k, t = t * T % P) {
        long long nx = a[j + k], ny = a[i + j + k] * t % P;
        a[j + k] = (nx + ny) % P;
        a[i + j + k] = (nx - ny + P) % P;
      }
    }
  }
  if (type == -1) {
    long long inv = quickpow(limi, P - 2);
    for (int i = 0; i < limi; ++i) a[i] = a[i] * inv % P;
  }
}
inline void init(int n, int m) {
  limi = 1;
  int L = 0;
  while (limi <= (n + m)) limi <<= 1, ++L;
  for (int i = 1; i < limi; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
}  // namespace jzpntt
struct Poly {
  vector<long long> v;
  Poly() {}
  Poly(int n) { v.resize(n); }
  Poly(long long a, long long b) {
    v.resize(2);
    v[0] = a;
    v[1] = b;
  }
  long long &operator[](int x) { return v[x]; }
  const long long &operator[](int x) const { return v[x]; }
  int size() const { return v.size(); }
  friend Poly operator+(const Poly &Lhs, const Poly &Rhs) {
    if (Lhs.size() > Rhs.size()) {
      Poly res(Lhs.size());
      for (int i = 0; i < Rhs.size(); ++i) res.v[i] = Add(Lhs.v[i], Rhs.v[i]);
      for (int i = Rhs.size(); i < Lhs.size(); ++i) res.v[i] = Lhs[i];
      return res;
    } else {
      Poly res(Rhs.size());
      for (int i = 0; i < Lhs.size(); ++i) res.v[i] = Add(Lhs.v[i], Rhs.v[i]);
      for (int i = Lhs.size(); i < Rhs.size(); ++i) res.v[i] = Rhs[i];
      return res;
    }
  }
  friend Poly operator*(const Poly &Lhs, const Poly &Rhs) {
    if (Lhs.size() < 20 || Rhs.size() < 20) {
      Poly res(Lhs.size() + Rhs.size() - 1);
      for (int i = 0; i < Lhs.size(); ++i)
        for (int j = 0; j < Rhs.size(); ++j)
          res[i + j] = (res[i + j] + Lhs[i] * Rhs[j]) % P;
      return res;
    }
    Poly res(Lhs.size() + Rhs.size() - 1);
    for (int i = 0; i < Lhs.size(); ++i) A[i] = Lhs[i];
    for (int i = 0; i < Rhs.size(); ++i) B[i] = Rhs[i];
    jzpntt::init(Lhs.size(), Rhs.size());
    jzpntt::ntt(A, 1);
    jzpntt::ntt(B, 1);
    for (int i = 0; i < limi; ++i) A[i] = A[i] * B[i] % P;
    jzpntt::ntt(A, -1);
    for (int i = 0; i < res.size(); ++i) res[i] = A[i];
    for (int i = 0; i < limi; ++i) A[i] = B[i] = 0;
    return res;
  }
};
long long ans;
int siz[101000];
long long f[101000], s[101000], fasiz;
pair<Poly, Poly> sol(int L, int R, vector<long long> &a, vector<long long> &b) {
  if (L == R) {
    Poly x(1, a[L]), y(b[L], fasiz * b[L] % P);
    return make_pair(x, y);
  }
  int mid = (L + R) >> 1;
  pair<Poly, Poly> jzp = sol(L, mid, a, b);
  Poly F = jzp.first, G = jzp.second;
  pair<Poly, Poly> zzz = sol(mid + 1, R, a, b);
  Poly FF = zzz.first, GG = zzz.second;
  return make_pair(F * FF, F * GG + FF * G);
}
void dfs(int cur, int faa) {
  vector<long long> a, b;
  siz[cur] = 1;
  long long sum = 0;
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to;
    if (to == faa) continue;
    dfs(to, cur);
    ADD(ans, sum * s[to] % P);
    ADD(sum, s[to]);
    a.push_back(siz[to]);
    b.push_back(s[to]);
    siz[cur] += siz[to];
  }
  fasiz = n - siz[cur];
  int sz = a.size();
  if (sz) {
    pair<Poly, Poly> pr = sol(0, sz - 1, a, b);
    Poly F = pr.first, G = pr.second;
    for (int i = 0; i <= min(sz, K); ++i)
      ADD(ans, get_c(K, i) * G[i] % P * jie[i] % P),
          ADD(f[cur], get_c(K, i) * F[i] % P * jie[i] % P);
  } else
    f[cur] = 1;
  ADD(sum, f[cur]);
  s[cur] = sum;
}
int main() {
  read(n), read(K);
  if (K == 1) {
    printf("%lld\n", (1ll * n * (n - 1) >> 1) % P);
    return 0;
  }
  init();
  for (int i = 1; i < n; ++i) {
    int u, v;
    read(u), read(v);
    addedge(u, v), addedge(v, u);
  }
  dfs(1, 0);
  printf("%lld\n", ans);
  return 0;
}