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>
const int MAXN = 262145;
const int mod = 998244353;
void reduce(int& x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (long long)a * b % mod; }
int pow(int a, int b, int res = 1) {
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) res = mul(res, a);
  return res;
}
int remod(long long x) {
  x %= mod;
  return x + (x >> 63 & mod);
}
int wn[MAXN], wt[MAXN];
int rev[MAXN], lim, dig;
void init(int sz) {
  lim = 1, dig = -1;
  while (lim < sz) lim <<= 1, ++dig;
  for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << dig;
  const int Wn = pow(3, (mod - 1) / lim);
  *wn = 1;
  for (int i = 1; i <= lim; ++i) wn[i] = mul(wn[i - 1], Wn);
}
void NTT(int* A, int typ) {
  for (int i = 0; i < lim; ++i)
    if (i < rev[i]) std::swap(A[i], A[rev[i]]);
  for (int mid = 1; mid != lim; mid <<= 1) {
    const int Wn = lim / mid / 2;
    for (int i = 0, W = 0; i != mid; ++i, W += Wn)
      wt[i] = wn[typ == 1 ? W : lim - W];
    for (int k = 0; k != lim; k += mid << 1) {
      const int* W = wt;
      for (int l = 0; l != mid; ++l) {
        const int X = A[l + k], Y = mul(*W++, A[l + k + mid]);
        reduce(A[l + k] += Y - mod);
        reduce(A[l + k + mid] = X - Y);
      }
    }
  }
  if (typ == -1) {
    const int liminv = pow(lim, mod - 2);
    for (int i = 0; i != lim; ++i) A[i] = mul(A[i], liminv);
  }
}
int head[MAXN], nxt[MAXN], to[MAXN], tot;
void adde(int b, int e) {
  nxt[++tot] = head[b];
  to[head[b] = tot] = e;
  nxt[++tot] = head[e];
  to[head[e] = tot] = b;
}
int n, K;
int fac[MAXN], inv[MAXN];
int dp[MAXN], sz[MAXN];
int li[MAXN], lp[MAXN], bak;
std::vector<int> operator*(const std::vector<int>& a,
                           const std::vector<int>& b) {
  static int ta[MAXN], tb[MAXN];
  const int ls = a.size(), rs = b.size();
  const int sz = ls + rs - 1;
  init(sz);
  std::copy(a.begin(), a.end(), ta);
  std::copy(b.begin(), b.end(), tb);
  std::fill(ta + ls, ta + lim, 0);
  std::fill(tb + rs, tb + lim, 0);
  NTT(ta, 1);
  NTT(tb, 1);
  for (int i = 0; i < lim; ++i) ta[i] = mul(ta[i], tb[i]);
  NTT(ta, -1);
  return std::vector<int>(ta, ta + sz);
}
std::vector<int> operator+(const std::vector<int>& a,
                           const std::vector<int>& b) {
  static int res[MAXN];
  const int ls = a.size(), rs = b.size();
  const int sz = std::max(ls, rs);
  std::fill(res, res + sz, 0);
  for (int i = 0; i != ls; ++i) res[i] = a[i];
  for (int i = 0; i != rs; ++i) reduce(res[i] += b[i] - mod);
  return std::vector<int>(res, res + sz);
}
std::pair<std::vector<int>, std::vector<int> > divcon(int l, int r) {
  if (l > r) return std::pair<std::vector<int>, std::vector<int> >({1}, {0});
  if (l == r)
    return std::pair<std::vector<int>, std::vector<int> >({1, li[l]}, {lp[l]});
  const int mid = l + r >> 1;
  std::pair<std::vector<int>, std::vector<int> > L = divcon(l, mid),
                                                 R = divcon(mid + 1, r);
  return std::pair<std::vector<int>, std::vector<int> >(
      L.first * R.first, L.first * R.second + L.second * R.first);
}
std::pair<int, int> solve(int up) {
  std::pair<std::vector<int>, std::vector<int> > rx = divcon(1, bak);
  const std::vector<int>& r1 = rx.first;
  std::vector<int> r2 = rx.second * std::vector<int>({1, up});
  int ans = 0, ans2 = 0;
  const int sz = r1.size();
  for (int i = 0; i < sz && i <= K; ++i) {
    reduce(ans += mul(r1[i], inv[K - i]) - mod);
    reduce(ans2 += mul(r2[i], inv[K - i]) - mod);
  }
  ans = mul(ans, fac[K]);
  ans2 = mul(ans2, fac[K]);
  return std::make_pair(ans, ans2);
}
int Ans = 0;
void dfs(int u, int fa = 0) {
  sz[u] = 1;
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa) {
      dfs(to[i], u);
      sz[u] += sz[to[i]];
      reduce(Ans += mul(dp[u], dp[to[i]]) - mod);
      reduce(dp[u] += dp[to[i]] - mod);
    }
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa) li[++bak] = sz[to[i]], lp[bak] = dp[to[i]];
  auto res = solve(n - sz[u]);
  reduce(dp[u] += res.first - mod);
  reduce(Ans += res.second - mod);
  bak = 0;
}
int main() {
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i != MAXN; ++i) {
    fac[i] = mul(fac[i - 1], i);
    inv[i] = mul(inv[mod % i], mod - mod / i);
  }
  for (int i = 2; i != MAXN; ++i) inv[i] = mul(inv[i - 1], inv[i]);
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n >> K;
  if (K == 1)
    return std::cout << ((long long)n * (n - 1) / 2) % mod << std::endl, 0;
  for (int i = 1, t1, t2; i < n; ++i) std::cin >> t1 >> t2, adde(t1, t2);
  dfs(1);
  std::cout << Ans << std::endl;
  return 0;
}