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 mod = 998244353;
const int N = 262150;
int n, K, x, y, Ans;
int siz[N], f[N], fs[N], fac[N], inv[N];
int rnk[N], f1[N], f2[N], g1[N], g2[N], F[N], G[N];
vector<int> vp1[N], vp2[N];
vector<pair<int, int> > vec[N];
int to[N], las[N], fir[N], cnt;
inline void add_edge(int u, int v) {
  to[++cnt] = v;
  las[cnt] = fir[u];
  fir[u] = cnt;
  to[++cnt] = u;
  las[cnt] = fir[v];
  fir[v] = cnt;
}
int ksm(int u, int v) {
  int res = 1;
  for (; v; v >>= 1, u = 1ll * u * u % mod)
    if (v & 1) res = 1ll * res * u % mod;
  return res;
}
void pre(int u) {
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i <= u; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[u] = ksm(fac[u], mod - 2);
  for (int i = u - 1; i >= 2; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int _(int u) { return u < mod ? u : u - mod; }
inline int __(int u) { return u < 0 ? u + mod : u; }
void ntt(int *t, int len, int opt) {
  int g = 3, g_ = ksm(g, mod - 2);
  for (int i = 0; i < len; i++)
    if (i < rnk[i]) swap(t[i], t[rnk[i]]);
  for (int i = 1; i < len; i <<= 1) {
    int wn = ksm(~opt ? g : g_, (mod - 1) / (i << 1));
    for (int j = 0, J = i << 1; j < len; j += J) {
      int w = 1;
      for (int k = j; k < i + j; k++, w = 1ll * w * wn % mod) {
        int r = 1ll * t[i + k] * w % mod;
        t[i + k] = __(t[k] - r);
        t[k] = _(t[k] + r);
      }
    }
  }
  if (~opt) return;
  int ny = ksm(len, mod - 2);
  for (int i = 0; i < len; i++) t[i] = 1ll * t[i] * ny % mod;
}
void solve(int l, int r, int c) {
  if (l == r) {
    vp1[l].resize(2);
    vp1[l][0] = 1;
    vp1[l][1] = vec[c][l].second;
    vp2[l].resize(2);
    vp2[l][0] = _(f[vec[c][l].first] + fs[vec[c][l].first]);
    vp2[l][1] =
        1ll * (f[vec[c][l].first] + fs[vec[c][l].first]) * (n - siz[c]) % mod;
    return;
  }
  int m = l + r >> 1;
  solve(l, m, c);
  solve(m + 1, r, c);
  m++;
  for (int i = 0; i < vp1[l].size(); i++) f1[i] = vp1[l][i];
  for (int i = 0; i < vp1[m].size(); i++) f2[i] = vp1[m][i];
  for (int i = 0; i < vp2[l].size(); i++) g1[i] = vp2[l][i];
  for (int i = 0; i < vp2[m].size(); i++) g2[i] = vp2[m][i];
  int len = 1, _2 = -1, Len = vp1[l].size() + vp1[m].size() - 1;
  while (len < Len) len <<= 1, _2++;
  for (int i = 0; i < len; i++) rnk[i] = (rnk[i >> 1] >> 1) | ((i & 1) << _2);
  for (int i = vp1[l].size(); i < len; i++) f1[i] = 0;
  for (int i = vp1[m].size(); i < len; i++) f2[i] = 0;
  for (int i = vp2[l].size(); i < len; i++) g1[i] = 0;
  for (int i = vp2[m].size(); i < len; i++) g2[i] = 0;
  ntt(f1, len, 1);
  ntt(f2, len, 1);
  ntt(g1, len, 1);
  ntt(g2, len, 1);
  for (int i = 0; i < len; i++) F[i] = 1ll * f1[i] * f2[i] % mod;
  for (int i = 0; i < len; i++)
    G[i] = _(1ll * f1[i] * g2[i] % mod + 1ll * f2[i] * g1[i] % mod);
  ntt(F, len, -1);
  ntt(G, len, -1);
  vp1[l].resize(Len);
  vp2[l].resize(Len);
  for (int i = 0; i < Len; i++) vp1[l][i] = F[i];
  for (int i = 0; i < Len; i++) vp2[l][i] = G[i];
}
void dfs(int u, int v) {
  siz[u] = 1;
  for (int i = fir[u]; i; i = las[i])
    if (to[i] != v) {
      dfs(to[i], u);
      siz[u] += siz[to[i]];
      vec[u].push_back(pair<int, int>(to[i], siz[to[i]]));
      fs[u] = _(fs[u] + _(fs[to[i]] + f[to[i]]));
    }
  if (!vec[u].size()) vec[u].push_back(pair<int, int>(0, 0));
  solve(0, vec[u].size() - 1, u);
  for (int i = 0; i <= min(K, (int)vp1[0].size() - 1); i++)
    f[u] = _(f[u] + 1ll * vp1[0][i] * fac[K] % mod * inv[K - i] % mod);
  x = _(x + f[u]);
  y = _(y + 1ll * f[u] * f[u] % mod);
  Ans = __(Ans - 1ll * f[u] * fs[u] % mod);
  for (int i = 0; i <= min(K, (int)vp2[0].size() - 1); i++)
    Ans = _(Ans + 1ll * vp2[0][i] * fac[K] % mod * inv[K - i] % mod);
}
int main() {
  scanf("%d%d", &n, &K);
  if (K == 1) {
    printf("%d\n", 1ll * n * (n - 1) % mod * ksm(2, mod - 2) % mod);
    return 0;
  }
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y);
  }
  pre(K);
  x = y = 0;
  dfs(1, 1);
  printf("%d\n",
         _(Ans + 1ll * __(1ll * x * x % mod - y) * ksm(2, mod - 2) % mod));
}