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;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int MAXN = (1 << 18) + 5;
const int maxn = (1 << 18);
const int mo = 998244353;
const int g0 = 3;
long long quickmi(long long x, long long tim) {
  long long ret = 1;
  for (; tim; tim /= 2, x = x * x % mo)
    if (tim & 1) ret = ret * x % mo;
  return ret;
}
long long add(long long x, long long y) {
  return x + y >= mo ? x + y - mo : x + y;
}
long long dec(long long x, long long y) { return x < y ? x - y + mo : x - y; }
long long mi[MAXN], A[MAXN], B[MAXN], ny;
int N;
long long js[MAXN], inv[MAXN];
void DFT(long long *a) {
  for (int i = 0, j = 0; i < N; i++) {
    if (i < j) swap(a[i], a[j]);
    int x = N >> 1;
    for (; (j ^ x) < j; x >>= 1) j ^= x;
    j ^= x;
  }
  for (int i = 1, d = 1; i < N; i <<= 1, d++)
    for (int j = 0; j < N; j += (i << 1))
      for (int k = 0; k < i; k++) {
        long long l = a[j + k], r = a[i + j + k] * mi[(maxn >> d) * k] % mo;
        a[i + j + k] = l < r ? l - r + mo : l - r;
        a[j + k] = l + r >= mo ? l + r - mo : l + r;
      }
}
void IDFT(long long *a) {
  DFT(a);
  reverse(a + 1, a + N);
  for (int i = 0; i <= N - 1; i++) a[i] = a[i] * ny % mo;
}
void prepare() {
  mi[0] = 1;
  mi[1] = quickmi(g0, (mo - 1) / maxn);
  for (int i = 2; i <= maxn; i++) mi[i] = mi[i - 1] * mi[1] % mo;
  js[0] = js[1] = 1;
  for (int i = 2; i <= maxn; i++) js[i] = js[i - 1] * i % mo;
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= maxn; i++)
    inv[i] = 1ll * (mo - mo / i) * inv[mo % i] % mo;
  for (int i = 2; i <= maxn; i++) inv[i] = inv[i] * inv[i - 1] % mo;
}
int n, k;
struct edge {
  int x, nxt;
} e[MAXN * 2];
int h[MAXN], tot;
void inse(int x, int y) {
  e[++tot].x = y;
  e[tot].nxt = h[x];
  h[x] = tot;
}
int siz[MAXN], fa[MAXN];
int lef[MAXN], rig[MAXN];
void dfs1(int x) {
  siz[x] = 1;
  for (int p = h[x]; p; p = e[p].nxt)
    if (!siz[e[p].x]) {
      fa[e[p].x] = x;
      rig[e[p].x] = lef[x];
      lef[x] = e[p].x;
      dfs1(e[p].x);
      siz[x] += siz[e[p].x];
    }
}
int key[MAXN], u;
long long poly[MAXN];
int st[MAXN], len[MAXN];
void getpoly() {
  int l = 0;
  for (int i = 1; i <= u; i++) {
    poly[++l] = key[i];
    st[i] = l;
    len[i] = 1;
  }
  N = 2;
  for (; u > 1; N <<= 1) {
    ny = quickmi(N, mo - 2);
    int u_ = 0;
    for (int i = 1; i <= u;) {
      int j = i + 1;
      for (; j <= u && len[i] + len[j] < N; j++) {
        for (int x = 0; x <= N - 1; x++) A[x] = B[x] = 0;
        A[0] = B[0] = 1;
        for (int x = 1; x <= len[i]; x++) A[x] = poly[st[i] + x - 1];
        for (int x = 1; x <= len[j]; x++) B[x] = poly[st[j] + x - 1];
        DFT(A), DFT(B);
        for (int x = 0; x <= N - 1; x++) A[x] = A[x] * B[x] % mo;
        IDFT(A);
        for (int x = 1; x <= len[i] + len[j]; x++) poly[st[i] + x - 1] = A[x];
        len[i] += len[j];
      }
      st[++u_] = st[i];
      len[u_] = len[i];
      i = j;
    }
    u = u_;
  }
}
long long tmp[MAXN];
long long val[MAXN];
long long f[MAXN], g[MAXN], vf[MAXN], vg[MAXN];
long long ans;
void dfs2(int x) {
  vf[x] = f[x];
  for (int y = lef[x]; y; y = rig[y]) {
    dfs2(y);
    vf[x] = add(vf[x], vf[y]);
  }
}
void dfs3(int x) {
  ans = add(ans, f[x] * vg[x] % mo);
  long long pre = vg[x];
  for (int y = lef[x]; y; y = rig[y]) {
    vg[y] = add(pre, g[y]);
    dfs3(y);
    pre = add(pre, vf[y]);
  }
}
int main() {
  n = get();
  k = get();
  if (k == 1) return printf("%I64d\n", 1ll * n * (n - 1) / 2 % mo), 0;
  for (int i = 2; i <= n; i++) {
    int x = get(), y = get();
    inse(x, y), inse(y, x);
  }
  prepare();
  dfs1(1);
  for (int ti = 1; ti <= n; ti++) {
    int st = ti;
    u = 0;
    for (int y = lef[st]; y; y = rig[y]) key[++u] = siz[y];
    if (fa[st]) key[++u] = n - siz[st];
    int pu = u;
    getpoly();
    int Len = len[1];
    poly[0] = 1;
    u = pu;
    sort(key + 1, key + 1 + u);
    int u_ = 1;
    for (int i = 2; i <= u; i++)
      if (key[i] > key[i - 1]) key[++u_] = key[i];
    u = u_;
    for (int i = 1; i <= u; i++) {
      int v = key[i];
      tmp[0] = poly[0];
      for (int j = 1; j <= Len; j++)
        tmp[j] = (poly[j] + mo - tmp[j - 1] * v % mo) % mo;
      val[v] = 0;
      for (int j = 0; j <= min(k, Len); j++)
        val[v] = add(val[v], tmp[j] * inv[k - j] % mo);
      val[v] = val[v] * js[k] % mo;
    }
    for (int y = lef[st]; y; y = rig[y]) g[y] = val[siz[y]];
    if (fa[st]) f[st] = val[n - siz[st]];
  }
  ans = 0;
  dfs2(1);
  dfs3(1);
  printf("%I64d\n", ans);
  return 0;
}