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>
using namespace std;
const int P = 998244353;
int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
int po(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = mu(k1, k1))
    if (k2 & 1) k3 = mu(k3, k1);
  return k3;
}
const int N = 100005, INF = 0X3F3F3F3F;
int n, K, fac[N], inv[N], ifac[N], sz[N];
int pp, lnk[N], nxt[N * 2], to[N * 2];
void ae(int k1, int k2) { to[++pp] = k2, nxt[pp] = lnk[k1], lnk[k1] = pp; }
int A(int k1, int k2) {
  if (k1 < 0 || k2 < 0 || k1 - k2 < 0) return 0;
  return mu(fac[k1], ifac[k1 - k2]);
}
int C(int k1, int k2) {
  if (k1 < 0 || k2 < 0 || k1 - k2 < 0) return 0;
  return mu(fac[k1], mu(ifac[k2], ifac[k1 - k2]));
}
int getlim(int x) {
  int y = 1;
  while (y <= x) y <<= 1;
  return y;
}
void NTT(vector<int>& a, int g, int lim) {
  a.resize(lim);
  for (int i = 0, j = 0; i < lim; ++i) {
    if (i < j) swap(a[i], a[j]);
    for (int k = (lim >> 1); (j ^= k) < k; k >>= 1)
      ;
  }
  vector<int> w(lim >> 1);
  w[0] = 1;
  for (int i = 1; i < lim; i <<= 1) {
    for (int j = 1, wn = po(g, (P - 1) / (i << 1)); j < i; ++j)
      w[j] = mu(w[j - 1], wn);
    for (int j = 0; j < lim; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = mu(a[i + j + k], w[k]);
        a[j + k] = ad(x, y), a[i + j + k] = su(x, y);
      }
    }
  }
  if (g != 3) {
    int t = po(lim, P - 2);
    for (int i = (0); i <= (lim - 1); ++i) a[i] = mu(a[i], t);
  }
}
vector<int> pmu(vector<int> a, vector<int> b, int nd = INF) {
  nd = min(nd, ((int)(a).size()) + ((int)(b).size()) - 1);
  int lim = getlim(nd);
  NTT(a, 3, lim), NTT(b, 3, lim);
  for (int i = (0); i <= (((int)(a).size()) - 1); ++i) a[i] = mu(a[i], b[i]);
  NTT(a, 332748118, lim);
  return a.resize(nd), a;
}
vector<int> pad(vector<int> a, vector<int> b) {
  if (((int)(a).size()) < ((int)(b).size())) swap(a, b);
  for (int i = (0); i <= (((int)(a).size()) - 1); ++i) a[i] = ad(a[i], b[i]);
  return a;
}
int f[N], sumf[N], cur;
namespace DC {
vector<int> F[20], G[20];
vector<int> A, B;
void bud(int k1, int k2, int k3) {
  if (k2 == k3) {
    F[k1] = {1, A[k2]};
    G[k1] = {sumf[B[k2]], mu(sumf[B[k2]], n - sz[cur])};
    return;
  }
  int mid = (k2 + k3) >> 1;
  bud(k1 + 1, k2, mid);
  F[k1] = F[k1 + 1];
  G[k1] = G[k1 + 1];
  bud(k1 + 1, mid + 1, k3);
  G[k1] = pad(pmu(F[k1], G[k1 + 1]), pmu(F[k1 + 1], G[k1]));
  F[k1] = pmu(F[k1], F[k1 + 1]);
}
}  // namespace DC
int ans, co1, co2;
void dfs(int k1, int k2) {
  sz[k1] = 1;
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      dfs(to[i], k1);
    }
  DC::A.clear();
  DC::B.clear();
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      sz[k1] += sz[to[i]];
      sumf[k1] = ad(sumf[k1], sumf[to[i]]);
      DC::A.push_back(sz[to[i]]);
      DC::B.push_back(to[i]);
    }
  if (!((int)(DC::A).size())) DC::A.push_back(0), DC::B.push_back(0);
  if (((int)(DC::A).size())) cur = k1, DC::bud(0, 0, ((int)(DC::A).size()) - 1);
  int len = min(K, ((int)(DC::F[0]).size()) - 1);
  for (int i = (0); i <= (len); ++i) {
    f[k1] = ad(f[k1], mu(A(K, i), DC::F[0][i]));
  }
  ans = su(ans, mu(f[k1], sumf[k1]));
  co1 = ad(co1, f[k1]);
  co2 = ad(co2, mu(f[k1], f[k1]));
  sumf[k1] = ad(sumf[k1], f[k1]);
  for (int i = (0); i <= (len); ++i) {
    ans = ad(ans, mu(A(K, i), DC::G[0][i]));
  }
}
int main() {
  fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  for (int i = (2); i <= (N - 1); ++i)
    fac[i] = mu(fac[i - 1], i), inv[i] = mu(P - P / i, inv[P % i]),
    ifac[i] = mu(ifac[i - 1], inv[i]);
  scanf("%d%d", &n, &K);
  if (K == 1) {
    printf("%d\n", mu(mu(n, n - 1), (P + 1) >> 1));
    return 0;
  }
  for (int i = (1); i <= (n - 1); ++i) {
    int k1, k2;
    scanf("%d%d", &k1, &k2);
    ae(k1, k2), ae(k2, k1);
  }
  dfs(1, 0);
  int rest = mu(su(mu(co1, co1), co2), (P + 1) >> 1);
  ans = ad(ans, rest);
  printf("%d\n", ans);
  return 0;
}