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 B = (1 << 15) - 1;
const double pi = acos(-1);
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 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 js[MAXN], inv[MAXN];
void prepare() {
  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;
}
namespace FFT {
struct comp {
  double x, y;
  comp(const double x_ = 0, const double y_ = 0) {
    x = x_;
    y = y_;
  }
} A[MAXN], B[MAXN], C[MAXN], D[MAXN];
comp operator+(comp a, comp b) { return comp(a.x + b.x, a.y + b.y); }
comp operator-(comp a, comp b) { return comp(a.x - b.x, a.y - b.y); }
comp operator*(comp a, comp b) {
  return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
comp conj(comp a) { return comp(a.x, -a.y); }
int N;
double cs[MAXN], si[MAXN];
void prepare() {
  for (int i = 0; i <= maxn; i++) {
    cs[i] = cos(pi * 2 / maxn * i);
    si[i] = sin(pi * 2 / maxn * i);
  }
}
void DFT(comp *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++) {
        comp l = a[j + k],
             r = a[i + j + k] * comp(cs[(maxn >> d) * k], si[(maxn >> d) * k]);
        a[i + j + k] = l - r;
        a[j + k] = l + r;
      }
}
void IDFT(comp *a) {
  DFT(a);
  reverse(a + 1, a + N);
  for (int i = 0; i <= N - 1; i++) a[i].x /= N, a[i].y /= N;
}
void multi(long long *a, long long *b, long long *c, int n, int m) {
  for (int i = 0; i <= N - 1; i++) A[i] = B[i] = comp(0, 0);
  for (int i = 0; i <= n; i++) A[i] = comp(a[i] >> 15, a[i] & 32767);
  for (int i = 0; i <= m; i++) B[i] = comp(b[i] >> 15, b[i] & 32767);
  DFT(A), DFT(B);
  for (int i = 0; i <= N - 1; i++) {
    comp x = A[i], y = A[i == 0 ? 0 : N - i];
    comp a0 = (x + conj(y)) * comp(0.5, 0), a1 = (x - conj(y)) * comp(0, -0.5);
    x = B[i], y = B[i == 0 ? 0 : N - i];
    comp b0 = (x + conj(y)) * comp(0.5, 0), b1 = (x - conj(y)) * comp(0, -0.5);
    C[i] = a0 * b0 + comp(0, 1) * a0 * b1;
    D[i] = a1 * b0 + comp(0, 1) * a1 * b1;
  }
  IDFT(C), IDFT(D);
  for (int i = 0; i <= n + m; i++) {
    long long v0 = C[i].x + 0.3, v1 = C[i].y + 0.3, v2 = D[i].x + 0.3,
              v3 = D[i].y + 0.3;
    v0 = ((v0 % mo) * 1073741824) % mo;
    v1 = ((v1 % mo) * 32768) % mo;
    v2 = ((v2 % mo) * 32768) % mo;
    v3 = v3 % mo;
    c[i] = add(v0, add(v1, add(v2, v3)));
  }
}
}  // namespace FFT
int n, k;
struct edge {
  int x, nxt;
} e[MAXN];
int h[MAXN], tot;
bool vis[MAXN];
int siz[MAXN];
void inse(int x, int y) {
  e[++tot].x = y;
  e[tot].nxt = h[x];
  h[x] = tot;
}
int fa[MAXN];
void dfs(int x) {
  vis[x] = 1;
  siz[x] = 1;
  for (int p = h[x]; p; p = e[p].nxt)
    if (!vis[e[p].x]) {
      fa[e[p].x] = x;
      dfs(e[p].x);
      siz[x] += siz[e[p].x];
    }
}
struct keypoint {
  int st, len;
} sec[MAXN];
int u;
int len;
long long poly[MAXN], val[MAXN], tmp[MAXN];
int key[MAXN];
long long tmpa[MAXN], tmpb[MAXN];
void solve_poly() {
  for (FFT::N = 2; u > 1; FFT::N <<= 1) {
    int u_ = 0;
    for (int i = 1; i <= u;) {
      int j = i + 1;
      for (; j <= u && sec[i].len + sec[j].len < FFT::N; j++) {
        for (int x = 1; x <= sec[i].len; x++) tmpa[x] = poly[sec[i].st + x - 1];
        for (int x = 1; x <= sec[j].len; x++) tmpb[x] = poly[sec[j].st + x - 1];
        tmpa[0] = tmpb[0] = 1;
        FFT::multi(tmpa, tmpb, tmp, sec[i].len, sec[j].len);
        sec[i].len += sec[j].len;
        for (int x = 1; x <= sec[i].len; x++) poly[sec[i].st + x - 1] = tmp[x];
      }
      sec[++u_] = sec[i];
      i = j;
    }
    u = u_;
  }
}
long long sum[MAXN];
long long f[MAXN], g[MAXN], vf[MAXN], vg[MAXN];
long long ans;
void dfs2(int x) {
  vf[x] = f[x];
  for (int p = h[x]; p; p = e[p].nxt)
    if (fa[e[p].x] == x) {
      int y = e[p].x;
      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 p = h[x]; p; p = e[p].nxt)
    if (fa[e[p].x] == x) {
      int y = e[p].x;
      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();
  FFT::prepare();
  dfs(1);
  for (int st = 1; st <= n; st++) {
    u = len = 0;
    if (siz[st] < n) {
      poly[len = 1] = n - siz[st];
      sec[++u].st = 1;
      sec[u].len = 1;
      key[u] = n - siz[st];
    }
    for (int p = h[st]; p; p = e[p].nxt)
      if (siz[st] > siz[e[p].x]) {
        key[++u] = poly[++len] = siz[e[p].x];
        sec[u].st = len;
        sec[u].len = 1;
      }
    int pu = u;
    solve_poly();
    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_;
    poly[0] = 1;
    for (int i = 1; i <= u; i++) {
      int v = key[i];
      tmp[0] = 1;
      for (int x = 1; x <= len; x++) tmp[x] = dec(poly[x], tmp[x - 1] * v % mo);
      val[v] = 0;
      for (int x = 0; x <= min(k, len - 1); x++)
        val[v] = (val[v] + tmp[x] * inv[k - x]) % mo;
      val[v] = val[v] * js[k] % mo;
    }
    if (siz[st] < n) f[st] = val[n - siz[st]];
    for (int p = h[st]; p; p = e[p].nxt)
      if (siz[st] > siz[e[p].x]) g[e[p].x] = val[siz[e[p].x]];
    for (int i = 0; i <= len; i++) poly[i] = 0;
  }
  dfs2(1);
  dfs3(1);
  cout << ans << endl;
  return 0;
}