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;
namespace NTT {
int mbase, base, root;
int w[1 << 19];
int rev[1 << 19];
int modPow(int b, int e) {
  int r = 1;
  while (e > 0) {
    if (e & 1) r = ((long long int)r * b) % 998244353;
    e >>= 1;
    b = ((long long int)b * b) % 998244353;
  }
  return r;
}
int setBase(int nbase) {
  int i, j;
  mbase = 1;
  while (!(998244353 & (1 << mbase))) mbase++;
  root = 2;
  while ((modPow(root, 1 << mbase) != 1) ||
         (modPow(root, 1 << (mbase - 1)) == 1))
    root++;
  base = nbase;
  for (i = 0; i < (1 << base); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
  w[0] = 0, w[1] = 1;
  for (i = 1; i < nbase; i++) {
    int z = modPow(root, 1 << (mbase - i - 1));
    for (j = (1 << (i - 1)); j < (1 << i); j++)
      w[j << 1] = w[j], w[(j << 1) | 1] = ((long long int)w[j] * z) % 998244353;
  }
  return 0;
}
int FFT(vector<int> &a, int inv) {
  int i, j, k;
  int l = 0;
  while ((1 << l) < a.size()) l++;
  int s = base - l;
  for (i = 0; i < a.size(); i++) {
    if (i < (rev[i] >> s)) swap(a[i], a[rev[i] >> s]);
  }
  for (k = 1; k < a.size(); k <<= 1) {
    for (i = 0; i < a.size(); i += (k << 1)) {
      for (j = 0; j < k; j++) {
        int z = ((long long int)a[i + j + k] * w[j + k]) % 998244353;
        a[i + j + k] = a[i + j] - z, a[i + j] = a[i + j] + z;
        if (a[i + j + k] < 0) a[i + j + k] += 998244353;
        if (a[i + j] >= 998244353) a[i + j] -= 998244353;
      }
    }
  }
  return 0;
}
vector<int> multiply(vector<int> A, vector<int> B) {
  int i, n = 1;
  while (n < A.size() + B.size() - 1) n <<= 1;
  vector<int> a(n, 0), b(n, 0);
  for (i = 0; i < A.size(); i++) a[i] = A[i];
  for (i = 0; i < B.size(); i++) b[i] = B[i];
  FFT(a, 0), FFT(b, 0);
  int x = modPow(n, 998244353 - 2);
  for (i = 0; i < n; i++)
    a[i] = ((((long long int)a[i] * b[i]) % 998244353) * x) % 998244353;
  reverse(a.begin() + 1, a.end()), FFT(a, 1), a.resize(A.size() + B.size() - 1);
  return a;
}
}  // namespace NTT
vector<int> adjList[100000];
int parent[100000], size[100000];
int doDFS(int u, int p) {
  int i;
  parent[u] = p, size[u] = 1;
  for (i = 0; i < adjList[u].size(); i++) {
    int v = adjList[u][i];
    if (v != p) size[u] += doDFS(v, u);
  }
  return size[u];
}
int down[100000], up[100000];
vector<int> mult(vector<vector<int> > &v, int l, int r) {
  if (l == r)
    return v[l];
  else if (l > r)
    return vector<int>(1, 1);
  int i;
  int mid = (l + r) / 2;
  vector<int> ll = mult(v, l, mid), rr = mult(v, mid + 1, r), ans;
  vector<int> temp = NTT::multiply(ll, rr);
  for (i = 0; i < temp.size(); i++) ans.push_back(temp[i] % 998244353);
  return ans;
}
vector<int> p[100000];
int ans = 0;
int doDFS2(int u, int p) {
  int i;
  int s = 0;
  for (i = 0; i < adjList[u].size(); i++) {
    int v = adjList[u][i];
    if (v != p) {
      doDFS2(v, u);
      down[u] += down[v], down[u] %= 998244353;
      ans += ((long long int)down[v] * up[v]) % 998244353, ans %= 998244353;
      ans += ((long long int)s * down[v]) % 998244353, ans %= 998244353;
      s += down[v], s %= 998244353;
    }
  }
  return 0;
}
int main() {
  int i;
  int n, k, a, b;
  scanf("%d %d", &n, &k);
  for (i = 0; i < n - 1; i++) {
    scanf("%d %d", &a, &b);
    a--, b--;
    adjList[a].push_back(b);
    adjList[b].push_back(a);
  }
  if (k == 1) {
    printf("%d\n", ((long long int)n * (n - 1) / 2) % 998244353);
    return 0;
  }
  int j, l;
  doDFS(0, -1);
  NTT::setBase(17);
  for (i = 0; i < n; i++) {
    vector<vector<int> > vv;
    for (j = 0; j < adjList[i].size(); j++) {
      int v = adjList[i][j];
      if (v != parent[i]) {
        vector<int> vvv(2);
        vvv[0] = size[v], vvv[1] = 1;
        vv.push_back(vvv);
      } else {
        vector<int> vvv(2);
        vvv[0] = n - size[i], vvv[1] = 1;
        vv.push_back(vvv);
      }
    }
    p[i] = mult(vv, 0, (int)vv.size() - 1);
  }
  for (i = 0; i < n; i++) {
    map<int, int> M;
    vector<int> poly = p[i];
    if (i > 0) {
      for (j = poly.size() - 1; j >= 1; j--)
        poly[j - 1] +=
            998244353 - (((long long int)(n - size[i]) * poly[j]) % 998244353),
            poly[j - 1] %= 998244353;
      for (j = 0; j < poly.size() - 1; j++) poly[j] = poly[j + 1];
      poly.pop_back();
    }
    long long int c = 1;
    for (j = 0; j < poly.size(); j++) {
      down[i] += (poly[poly.size() - j - 1] * c) % 998244353,
          down[i] %= 998244353;
      c *= k - j, c %= 998244353;
    }
    M[n - size[i]] = down[i];
    for (j = 0; j < adjList[i].size(); j++) {
      int v = adjList[i][j];
      if (v != parent[i]) {
        if (M.count(size[v]))
          up[v] = M[size[v]];
        else {
          vector<int> poly = p[i];
          for (l = poly.size() - 1; l >= 1; l--)
            poly[l - 1] +=
                998244353 - (((long long int)size[v] * poly[l]) % 998244353),
                poly[l - 1] %= 998244353;
          for (l = 0; l < poly.size() - 1; l++) poly[l] = poly[l + 1];
          poly.pop_back();
          long long int c = 1;
          for (l = 0; l < poly.size(); l++) {
            up[v] += (poly[poly.size() - l - 1] * c) % 998244353,
                up[v] %= 998244353;
            c *= k - l, c %= 998244353;
          }
          M[size[v]] = up[v];
        }
      }
    }
  }
  doDFS2(0, -1);
  printf("%d\n", ans);
  return 0;
}