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 int read() {
  register int X = 0;
  register char ch = 0;
  while (ch < 48 || ch > 57) ch = getchar();
  while (ch >= 48 && ch <= 57) X = X * 10 + (ch ^ 48), ch = getchar();
  return X;
}
long long powM(long long a, int t = 998244353 - 2) {
  long long ans = 1;
  while (t) {
    if (t & 1) ans = ans * a % 998244353;
    a = a * a % 998244353;
    t >>= 1;
  }
  return ans;
}
int r[135000 << 2];
const long long invG = powM(3);
void NTT(long long *f, bool op, int n) {
  for (int i = 0; i < n; i++)
    if (r[i] < i) swap(f[r[i]], f[i]);
  for (int len = 1; len < n; len <<= 1) {
    int w = powM(op == 1 ? 3 : invG, (998244353 - 1) / len / 2);
    for (int p = 0; p < n; p += len + len) {
      long long buf = 1;
      for (int i = p; i < p + len; i++) {
        int sav = f[i + len] * buf % 998244353;
        f[i + len] = (f[i] - sav + 998244353) % 998244353;
        f[i] = (f[i] + sav) % 998244353;
        buf = buf * w % 998244353;
      }
    }
  }
}
long long Ak[135000], ans, ans2;
vector<int> g[135000];
long long _s[135000 << 1], _s2[135000 << 1], S[135000];
struct Data {
  long long *p, *p2;
  int c;
} a[135000];
int n, k, siz[135000];
void dfs(int u, int fa) {
  siz[u] = 1;
  for (int i = 0, v; i < g[u].size(); i++)
    if ((v = g[u][i]) != fa) dfs(v, u);
  int tn = 0;
  for (int i = 0, v; i < g[u].size(); i++)
    if ((v = g[u][i]) != fa) {
      siz[u] += siz[v];
      S[u] = (S[u] + S[v]) % 998244353;
      a[++tn].c = 2;
      a[tn].p2 = _s2 + tn * 2 - 2;
      a[tn].p = _s + tn * 2 - 2;
      a[tn].p[0] = 1;
      a[tn].p[1] = siz[v];
      a[tn].p2[0] = S[v];
      a[tn].p2[1] = 0;
    }
  if (!tn) {
    ans -= (S[u] = 1);
    return;
  }
  static long long s1[135000 << 1], s2[135000 << 1], s3[135000 << 1],
      s4[135000 << 1];
  while (tn > 1) {
    for (int i = 2; i <= tn; i += 2) {
      memcpy(s1, a[i - 1].p, sizeof(long long) * a[i - 1].c);
      memcpy(s2, a[i - 1].p2, sizeof(long long) * a[i - 1].c);
      memcpy(s3, a[i].p, sizeof(long long) * a[i].c);
      memcpy(s4, a[i].p2, sizeof(long long) * a[i].c);
      int m = a[i - 1].c + a[i - 1].c - 1, n = 1;
      for (; n < m; n <<= 1)
        ;
      for (int i = 0; i < n; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
      NTT(s1, 1, n);
      NTT(s2, 1, n);
      NTT(s3, 1, n);
      NTT(s4, 1, n);
      for (int i = 0; i < n; i++) {
        s4[i] = (s1[i] * s4[i] + s2[i] * s3[i]) % 998244353;
        s1[i] = s1[i] * s3[i] % 998244353;
      }
      NTT(s1, 0, n);
      NTT(s4, 0, n);
      long long invn = powM(n);
      a[i >> 1].c = min(m, k + 1);
      for (int j = 0; j < a[i >> 1].c; j++) {
        a[i - 1].p[j] = s1[j] * invn % 998244353;
        a[i - 1].p2[j] = s4[j] * invn % 998244353;
      }
      memset(s1, 0, sizeof(long long) * (n + 2));
      memset(s2, 0, sizeof(long long) * (n + 2));
      memset(s3, 0, sizeof(long long) * (n + 2));
      memset(s4, 0, sizeof(long long) * (n + 2));
      a[i >> 1].p = a[i - 1].p;
      a[i >> 1].p2 = a[i - 1].p2;
    }
    if (tn & 1) a[(tn + 1) >> 1] = a[tn];
    tn = (tn + 1) >> 1;
  }
  long long sav = 0;
  for (int i = 0; i < min(k + 1, a[1].c); i++)
    sav = (sav + Ak[i] * a[1].p[i]) % 998244353;
  S[u] = (S[u] + sav) % 998244353;
  ans = (ans - sav * (2 * S[u] - sav)) % 998244353;
  memcpy(s1, a[1].p2, sizeof(long long) * a[1].c);
  for (int i = a[1].c - 1; i >= 0; i--)
    s1[i + 1] = (s1[i + 1] + s1[i] * (n - siz[u])) % 998244353;
  for (int i = 0; i < min(k + 1, a[1].c); i++)
    ans2 = (ans2 + Ak[i] * s1[i]) % 998244353;
  memset(s1, 0, sizeof(long long) * (a[1].c + 2));
}
int main() {
  n = read();
  k = read();
  if (k == 1) {
    printf("%d", (int)((1ll * n * (n - 1) / 2) % 998244353));
    return 0;
  }
  Ak[0] = 1;
  for (int i = 1; i <= k; i++) Ak[i] = Ak[i - 1] * (k - i + 1) % 998244353;
  for (int i = 1, ft, to; i < n; i++) {
    ft = read();
    to = read();
    g[ft].push_back(to);
    g[to].push_back(ft);
  }
  dfs(1, 0);
  ans = (ans + S[1] * S[1]) % 998244353 * 499122177ll % 998244353;
  printf("%d", (int)((ans + ans2) % 998244353));
  return 0;
}