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;
inline long long rd() {
  long long x = 0, w = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), w = -1;
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  return x * w;
}
const int N = 262150, P = 998244353, iv2 = (P + 1) / 2;
int n, K, r1, r2, ans, sz[N], f[N], fs[N], fac[N], ifac[N], r[N], w[N];
vector<int> G[N];
vector<pair<int, int> > V[N];
inline int pw(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = 1ll * a * a % P)
    if (b & 1) r = 1ll * r * a % P;
  return r;
}
inline void ntt(int n, int* a, int f) {
  int l = 0;
  while ((1 << l) < n) l++;
  for (int i = (1); i < (n); ++i) r[i] = r[i >> 1] >> 1 | (i & 1) << (l - 1);
  for (int i = (0); i < (n); ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    int wn = pw(3, f == 1 ? (P - 1) / i : P - 1 - (P - 1) / i);
    w[0] = 1;
    for (int j = (1); j < ((i >> 1)); ++j) w[j] = 1ll * w[j - 1] * wn % P;
    for (int j = 0; j < n; j += i) {
      int *x = a + j, *y = a + j + (i >> 1);
      for (int k = (0); k < ((i >> 1)); ++k) {
        int v = 1ll * y[k] * w[k] % P;
        y[k] = (x[k] + P - v) % P;
        x[k] = (x[k] + v) % P;
      }
    }
  }
  if (f == -1) {
    int ivn = pw(n, P - 2);
    for (int i = (0); i < (n); ++i) a[i] = 1ll * a[i] * ivn % P;
  }
}
int f1[N], f2[N], g1[N], g2[N], A[N], B[N];
vector<int> v1[N], v2[N];
void sol(int l, int r, int x) {
  if (l == r) {
    int y = V[x][l].first;
    v1[l].resize(2);
    v1[l][0] = 1;
    v1[l][1] = V[x][l].second;
    v2[l].resize(2);
    v2[l][0] = (f[y] + fs[y]) % P;
    v2[l][1] = 1ll * (n - sz[x]) * (f[y] + fs[y]) % P;
    return;
  }
  int m = l + r >> 1;
  sol(l, m, x);
  sol(m + 1, r, x);
  m++;
  int n = r - l + 2, nn = 1;
  while (nn < n) nn <<= 1;
  for (int i = (0); i < (nn); ++i) f1[i] = f2[i] = g1[i] = g2[i] = 0;
  for (int i = 0; i < (v1[l]).size(); ++i) f1[i] = v1[l][i], g1[i] = v2[l][i];
  for (int i = 0; i < (v1[m]).size(); ++i) f2[i] = v1[m][i], g2[i] = v2[m][i];
  ntt(nn, f1, 1);
  ntt(nn, f2, 1);
  ntt(nn, g1, 1);
  ntt(nn, g2, 1);
  for (int i = (0); i < (nn); ++i)
    A[i] = 1ll * f1[i] * f2[i] % P,
    B[i] = (1ll * f1[i] * g2[i] + 1ll * g1[i] * f2[i]) % P;
  ntt(nn, A, -1);
  ntt(nn, B, -1);
  v1[l].resize(n);
  v2[l].resize(n);
  for (int i = (0); i < (n); ++i) v1[l][i] = A[i], v2[l][i] = B[i];
}
void dfs(int x, int p) {
  sz[x] = 1;
  for (int y : G[x])
    if (y != p) {
      dfs(y, x);
      sz[x] += sz[y];
      V[x].push_back(make_pair(y, sz[y]));
      fs[x] = (1ll * fs[x] + fs[y] + f[y]) % P;
    }
  if (!V[x].size()) V[x].push_back(make_pair(0, 0));
  sol(0, V[x].size() - 1, x);
  int k = min(K, (int)v1[0].size() - 1);
  for (int i = (0); i <= (k); ++i)
    f[x] = (f[x] + 1ll * v1[0][i] * fac[K] % P * ifac[K - i]) % P;
  r1 = (r1 + f[x]) % P;
  r2 = (r2 + 1ll * f[x] * f[x]) % P;
  ans = (ans + P - 1ll * f[x] * fs[x] % P) % P;
  for (int i = (0); i <= (k); ++i)
    ans = (ans + 1ll * v2[0][i] * fac[K] % P * ifac[K - i]) % P;
}
int main() {
  n = rd();
  K = rd();
  fac[0] = 1;
  for (int i = (1); i <= (K); ++i) fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[K] = pw(fac[K], P - 2);
  for (int i = (K); i >= (1); --i) ifac[i - 1] = 1ll * ifac[i] * i % P;
  if (K == 1) {
    printf("%d\n", 1ll * n * (n - 1) / 2 % P);
    return 0;
  }
  for (int i = (1); i <= (n - 1); ++i) {
    int u = rd(), v = rd();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 1);
  printf("%d\n", (ans + 1ll * (1ll * r1 * r1 % P + P - r2) * iv2 % P) % P);
  return 0;
}