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 * 10;
const int MOD = 998244353;
const int G = 3;
const int GI = 332748118;
int add(int x, int y) {
  x = x + y;
  return x >= MOD ? x - MOD : x;
}
int mul(int x, int y) { return (long long)x * y % MOD; }
int dec(int x, int y) {
  x = x - y;
  return x < 0 ? x + MOD : x;
}
int Pow(int x, int y) {
  if (y == 1) return x;
  int lalal = Pow(x, y >> 1);
  lalal = mul(lalal, lalal);
  if (y & 1) lalal = mul(lalal, x);
  return lalal;
}
struct qq {
  int x, y, last;
} E[N * 2];
int num, last[N];
void init(int x, int y) {
  E[++num].x = x;
  E[num].y = y;
  E[num].last = last[x];
  last[x] = num;
}
int n, k;
int JC[N], inv[N];
int tot[N], fa[N];
vector<int> e[N];
void dfs(int x) {
  tot[x] = 1;
  for (int u = last[x]; u != -1; u = E[u].last) {
    int y = E[u].y;
    if (y == fa[x]) continue;
    e[x].push_back(y);
    fa[y] = x;
    dfs(y);
    tot[x] = tot[x] + tot[y];
  }
}
void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  solve(mid + 1, r);
}
int A[N], a[N];
int bin[N];
vector<int> vec[N];
void NTT(int *a, int n, int o) {
  for (int u = 0; u < n; u++)
    bin[u] = (bin[u >> 1] >> 1) | ((u & 1) * (n >> 1));
  for (int u = 0; u < n; u++)
    if (u < bin[u]) swap(a[u], a[bin[u]]);
  for (int u = 1; u < n; u <<= 1) {
    int wn = Pow(o == 1 ? G : GI, (MOD - 1) / (u << 1)), w, t;
    for (int i = 0; i < n; i = i + (u << 1)) {
      w = 1;
      for (int j = 0; j < u; j++) {
        t = mul(w, a[u + i + j]);
        a[u + i + j] = dec(a[i + j], t);
        a[i + j] = add(a[i + j], t);
        w = mul(w, wn);
      }
    }
  }
  if (o == -1) {
    int inv = Pow(n, MOD - 2);
    for (int u = 0; u < n; u++) a[u] = mul(a[u], inv);
  }
}
void solve(int *a, int ln, int l, int r) {
  if (l == r) {
    a[0] = 1;
    a[1] = A[l];
    return;
  }
  int mid = (l + r) >> 1;
  int g0[ln + 10], g1[ln + 10];
  memset(g0, 0, sizeof(g0));
  memset(g1, 0, sizeof(g1));
  solve(g0, ln >> 1, l, mid);
  solve(g1, ln >> 1, mid + 1, r);
  NTT(g0, ln, 1);
  NTT(g1, ln, 1);
  for (int u = 0; u < ln; u++) a[u] = mul(g0[u], g1[u]);
  NTT(a, ln, -1);
}
int g[N];
bool cmp(int x, int y) { return tot[x] < tot[y]; }
int calc1(int x) {
  int siz = vec[x].size() - 1, lalal = 0;
  for (int u = 0; u <= min(siz, k); u++)
    lalal = add(lalal, mul(mul(vec[x][u], JC[k]), inv[k - u]));
  return lalal;
}
void Dec(int x, int xx) {
  int siz = vec[x].size() - 1;
  for (int u = 1; u <= siz; u++)
    vec[x][u] = dec(vec[x][u], mul(vec[x][u - 1], xx));
}
void Add(int x, int xx) {
  int siz = vec[x].size() - 1;
  for (int u = siz - 1; u >= 0; u--)
    vec[x][u + 1] = add(vec[x][u + 1], mul(vec[x][u], xx));
}
int ans = 0;
void calc(int x) {
  int siz = e[x].size();
  sort(e[x].begin(), e[x].end(), cmp);
  int lst = -1, t = 0;
  for (int u = 0; u < siz; u++) {
    int y = e[x][u];
    calc(y);
    if (tot[y] != lst) {
      if (lst != -1) Add(x, lst);
      Dec(x, tot[y]);
      t = calc1(x);
      lst = tot[y];
    }
    ans = add(ans, mul(g[y], g[x]));
    ans = add(ans, mul(g[y], t));
    g[x] = add(g[x], g[y]);
  }
  if (lst != -1) Add(x, lst);
  Dec(x, n - tot[x]);
  t = calc1(x);
  g[x] = add(g[x], t);
}
int main() {
  num = 0;
  memset(last, -1, sizeof(last));
  scanf("%d%d", &n, &k);
  if (k == 1) return printf("%lld", (1ll * (n - 1ll) * n / 2ll) % MOD), 0;
  JC[0] = 1;
  for (int u = 1; u <= k; u++) JC[u] = mul(JC[u - 1], u);
  inv[k] = Pow(JC[k], MOD - 2);
  for (int u = k; u >= 0; u--) inv[u - 1] = mul(inv[u], u);
  for (int u = 1; u < n; u++) {
    int x, y;
    scanf("%d%d", &x, &y);
    init(x, y);
    init(y, x);
  }
  dfs(1);
  for (int u = 1; u <= n; u++) {
    int nn = 0;
    int siz = e[u].size();
    for (int i = 0; i < siz; i++) {
      nn++;
      A[nn] = tot[e[u][i]];
    }
    A[++nn] = n - tot[u];
    int ln = 1;
    while (ln <= 2 * (nn + 1)) ln <<= 1;
    solve(a, ln, 1, nn);
    for (int i = 0; i <= nn; i++) {
      vec[u].push_back(a[i]);
    }
  }
  calc(1);
  printf("%d\n", ans);
  return 0;
}