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 = 100005, P = 998244353, maxn = 1 << 17 | 1;
int fpow(int a, int b) {
  long long d = 1, x = a;
  while (b) {
    if (b & 1) d = d * x % P;
    x = x * x % P;
    b >>= 1;
  }
  return d;
}
int n, K, inv[N], fac[N], ifac[N], sz[N], son[N], fe[N], cnt, se, jk, sum[N];
vector<int> G[N];
namespace poly {
int Len, sz, rev[maxn], w[maxn];
void prepare(int n) {
  for (Len = 1, sz = 0; Len <= n; Len <<= 1, sz++)
    ;
  for (int i = 0; i < Len; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
  int wn = fpow(3, (P - 1) / Len);
  w[Len / 2] = 1;
  for (int i = Len / 2 + 1; i < Len; i++) w[i] = 1LL * w[i - 1] * wn % P;
  for (int i = Len / 2 - 1; i >= 0; i--) w[i] = w[i << 1];
}
void DFT(int n, int *a, int T) {
  static unsigned long long F[maxn];
  int shift = sz - __builtin_ctz(n), x;
  for (int i = 0; i < n; i++) F[rev[i] >> shift] = a[i];
  for (int l = 1; l < n; l <<= 1)
    for (int i = 0; i < n; i += l << 1)
      for (int j = 0; j < l; j++) {
        x = F[i + j + l] * w[j + l] % P;
        F[i + j + l] = F[i + j] + P - x;
        F[i + j] += x;
      }
  for (int i = 0; i < n; i++) a[i] = F[i] % P;
  if (T) {
    x = fpow(n, P - 2);
    for (int i = 0; i < n; i++) a[i] = (long long)a[i] * x % P;
    reverse(a + 1, a + n);
  }
}
}  // namespace poly
vector<int> fft(int l, int r) {
  if (l == r) return vector<int>{1, sz[son[l]]};
  static int a[maxn], b[maxn];
  int mid = (l + r) / 2;
  vector<int> L = fft(l, mid), R = fft(mid + 1, r);
  int ls = L.size(), rs = R.size(), n = ls + rs - 1, len;
  if (n <= 300) {
    for (int i = 0; i < n; i++) a[i] = 0;
    for (int i = 0; i < ls; i++)
      for (int j = 0; j < rs; j++)
        a[i + j] = (a[i + j] + (long long)L[i] * R[j]) % P;
  } else {
    for (len = 1; len < n; len <<= 1)
      ;
    for (int i = 0; i < len; i++) {
      a[i] = (i < ls ? L[i] : 0);
      b[i] = (i < rs ? R[i] : 0);
    }
    poly::DFT(len, a, 0);
    poly::DFT(len, b, 0);
    for (int i = 0; i < len; i++) a[i] = (long long)a[i] * b[i] % P;
    poly::DFT(len, a, 1);
  }
  return vector<int>(a, a + n);
}
vector<int> div(vector<int> F, int a) {
  int l = F.size(), I = inv[a];
  vector<int> f(l - 1);
  for (int i = f.size() - 1; i >= 0; i--) {
    int t = (long long)F[i + 1] * I % P;
    f[i] = t;
    F[i] = (F[i] - t + P) % P;
  }
  return f;
}
vector<int> wv[N];
void dfs(int u, int fa) {
  sz[u] = 1;
  for (int v : G[u])
    if (v ^ fa) dfs(v, u), sz[u] += sz[v];
  cnt = 0;
  for (int v : G[u])
    if (v ^ fa) son[++cnt] = v;
  vector<int> &F = wv[u];
  F = (cnt ? fft(1, cnt) : vector<int>{1});
  int l = F.size(), tmp = 0;
  for (int i = 0; i < l && i <= K; i++)
    tmp = (tmp + (long long)F[i] * ifac[K - i]) % P;
  fe[u] = (long long)tmp * fac[K] % P;
}
void dfs1(int u, int fa) {
  for (int v : G[u])
    if (v ^ fa) {
      dfs1(v, u);
      se = (se + (long long)sum[u] * sum[v]) % P;
      sum[u] = (sum[u] + sum[v]) % P;
    }
  sum[u] = (sum[u] + fe[u]) % P;
}
bool cmp(int x, int y) { return sz[x] < sz[y]; }
void dfs2(int u, int fa) {
  for (int v : G[u])
    if (v ^ fa) dfs2(v, u);
  cnt = 0;
  for (int v : G[u])
    if (v ^ fa) son[++cnt] = v;
  sort(son + 1, son + 1 + cnt, cmp);
  vector<int> F = wv[u], G;
  if (sz[u] < n) {
    int t = n - sz[u];
    F.resize(F.size() + 1);
    for (int i = F.size() - 1; i >= 1; i--)
      F[i] = (F[i] + (long long)F[i - 1] * t) % P;
  }
  int tmp = 0;
  for (int k = 1; k <= cnt; k++) {
    if (sz[son[k]] != sz[son[k - 1]]) {
      G = div(F, sz[son[k]]);
      tmp = 0;
      for (int i = 0, l = G.size(); i < l && i <= K; i++)
        tmp = (tmp + (long long)G[i] * ifac[K - i]) % P;
      tmp = (long long)tmp * fac[K] % P;
    }
    jk = (jk + (long long)tmp * sum[son[k]]) % P;
  }
}
int main() {
  scanf("%d%d", &n, &K);
  if (K == 1) {
    jk = (long long)n * (n - 1) / 2 % P;
    printf("%d", jk);
    return 0;
  }
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  poly::prepare(n);
  inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= max(n, K); i++) {
    fac[i] = (long long)fac[i - 1] * i % P;
    inv[i] = (long long)(P - P / i) * inv[P % i] % P;
    ifac[i] = (long long)ifac[i - 1] * inv[i] % P;
  }
  dfs(1, 0);
  dfs1(1, 0);
  dfs2(1, 0);
  printf("%d\n", (se + jk) % P);
  return 0;
}