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 N = 1.1e5, Mod = 998244353;
int n, m, cnt = 1, ans, hd[N], sz[N], d[N], sum[N], *g[N * 4], fac[N], inv[N],
          numinv[N];
struct edge {
  int v, sz, pw, cnt, nxt;
} e[N * 2];
int Pow(int x, int y) {
  if (y < 0) y += Mod - 1;
  int ret = 1;
  while (y) {
    if (y & 1) ret = (long long)ret * x % Mod;
    x = (long long)x * x % Mod, y >>= 1;
  }
  return ret;
}
void fft(int *a, int *r, int len, int typ) {
  for (int i = 0; i < len; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < len; i <<= 1)
    for (int j = 0, s = i << 1, wn = Pow(3, typ * (Mod - 1) / s); j < len;
         j += s)
      for (int k = 0, w = 1; k < i; k++, w = (long long)w * wn % Mod) {
        int &a1 = a[j + k], &a2 = a[j + k + i], a3 = (long long)a2 * w % Mod;
        a2 = (a1 - a3) % Mod, a1 = (a1 + a3) % Mod;
      }
  if (typ == -1)
    for (int i = 0, iv = Pow(len, -1); i < len; i++)
      a[i] = (long long)a[i] * iv % Mod;
}
void FFT(int *ret, const int *A, const int *B, int pa, int pb, int pc, int pd) {
  static int L, C, a[N * 4], b[N * 4], r[N * 4];
  for (L = 1, C = 0; L <= pc; L <<= 1, C++)
    ;
  for (int i = 0; i < L; i++) r[i] = r[i >> 1] >> 1 | (i & 1) << (C - 1);
  memcpy(a, A, (4 * (pa + 1)));
  memset(a + pa + 1, 0, (4 * (L - pa - 1)));
  memcpy(b, B, (4 * (pb + 1)));
  memset(b + pb + 1, 0, (4 * (L - pb - 1)));
  fft(a, r, L, 1), fft(b, r, L, 1);
  for (int i = 0; i < L; i++) a[i] = (long long)a[i] * b[i] % Mod;
  fft(a, r, L, -1);
  memcpy(ret, a, (4 * (pd + 1)));
}
void adde(int u, int v) { e[++cnt] = (edge){v, 0, 0, 0, hd[u]}, hd[u] = cnt; }
void multi(int *a, int l, int r, int x) {
  int *&G = g[x];
  if (G) delete[] G;
  G = new int[r - l + 2];
  if (l == r) {
    G[0] = 1, G[1] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  multi(a, l, mid, x << 1), multi(a, mid + 1, r, x << 1 | 1);
  FFT(G, g[x << 1], g[x << 1 | 1], mid - l + 1, r - mid, r - l + 1, r - l + 1);
}
int P(int x, int y) { return (long long)fac[x] * inv[x - y] % Mod; }
int cal(int *a, int p) {
  int ret = 0;
  for (int i = 0; i <= m && i <= p; i++)
    if (!(m == 1 && i == 1)) ret = (ret + (long long)a[i] * P(m, i)) % Mod;
  return ret;
}
void dfs(int u, int fa) {
  int *a, *f, p = 0;
  a = new int[d[u] + 1];
  f = new int[d[u] + 1];
  sz[u] = 1;
  for (int i = hd[u], v; i; i = e[i].nxt) {
    if ((v = e[i].v) == fa) continue;
    dfs(v, u), sz[u] += sz[v];
    a[++p] = sz[v];
    ans = (ans + (long long)sum[u] * sum[v]) % Mod;
    sum[u] = (sum[u] + sum[v]) % Mod;
  }
  if (p)
    multi(a, 1, p, 1), memcpy(f, g[1], (4 * (p + 1)));
  else
    f[0] = 1;
  sum[u] = (sum[u] + cal(f, p)) % Mod;
  if (fa) {
    f[d[u]] = 0;
    for (int i = d[u] - 1; i >= 0; i--)
      f[i + 1] = (f[i + 1] + (long long)f[i] * (n - sz[u])) % Mod;
  }
  map<int, int> mp;
  for (int i = hd[u], v; i; i = e[i].nxt) {
    if ((v = e[i].v) == fa) continue;
    pair<map<int, int>::iterator, bool> it = mp.insert(make_pair(sz[v], 0));
    if (!it.second) {
      ans = (ans + (long long)it.first->second * sum[v]) % Mod;
      continue;
    }
    a[d[u]] = 0;
    for (int j = d[u]; j; j--)
      a[j - 1] = (long long)f[j] * numinv[sz[v]] % Mod,
            f[j - 1] = (f[j - 1] - a[j - 1]) % Mod;
    it.first->second = cal(a, d[u] - 1);
    ans = (ans + (long long)it.first->second * sum[v]) % Mod;
    for (int j = d[u] - 1; j >= 0; j--)
      f[j + 1] = (a[j + 1] + (long long)a[j] * sz[v]) % Mod;
    f[0] = a[0];
  }
  delete[] a;
  delete[] f;
}
void init() {
  fac[0] = fac[1] = numinv[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++)
    numinv[i] = (long long)-Mod / i * numinv[Mod % i] % Mod,
    fac[i] = (long long)fac[i - 1] * i % Mod,
    inv[i] = (long long)inv[i - 1] * numinv[i] % Mod;
}
int main() {
  cin >> n >> m;
  init();
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    adde(u, v), adde(v, u);
    d[u]++, d[v]++;
  }
  dfs(1, 0);
  cout << (ans + Mod) % Mod << endl;
  return 0;
}