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 md = 998244353;
inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}
inline int mul(int a, int b) {
  return (int)((long long)a * b % md);
  unsigned long long x = (long long)a * b;
  unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
  asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(md));
  return m;
}
inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
inline int inv(int a) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}
namespace ntt {
int base = 1;
vector<int> roots = {0, 1};
vector<int> rev = {0, 1};
int max_base = -1;
int root = -1;
void init() {
  int tmp = md - 1;
  max_base = 0;
  while (tmp % 2 == 0) {
    tmp /= 2;
    max_base++;
  }
  root = 2;
  while (true) {
    if (power(root, 1 << max_base) == 1) {
      if (power(root, 1 << (max_base - 1)) != 1) {
        break;
      }
    }
    root++;
  }
}
void ensure_base(int nbase) {
  if (max_base == -1) {
    init();
  }
  if (nbase <= base) {
    return;
  }
  assert(nbase <= max_base);
  rev.resize(1 << nbase);
  for (int i = 0; i < (1 << nbase); i++) {
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = power(root, 1 << (max_base - 1 - base));
    for (int i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      roots[(i << 1) + 1] = mul(roots[i], z);
    }
    base++;
  }
}
void fft(vector<int> &a) {
  int n = (int)a.size();
  assert((n & (n - 1)) == 0);
  int zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; i++) {
    if (i < (rev[i] >> shift)) {
      swap(a[i], a[rev[i] >> shift]);
    }
  }
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += 2 * k) {
      for (int j = 0; j < k; j++) {
        int x = a[i + j];
        int y = mul(a[i + j + k], roots[j + k]);
        a[i + j] = x + y - md;
        if (a[i + j] < 0) a[i + j] += md;
        a[i + j + k] = x - y + md;
        if (a[i + j + k] >= md) a[i + j + k] -= md;
      }
    }
  }
}
vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) {
  int need = (int)(a.size() + b.size() - 1);
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  a.resize(sz);
  b.resize(sz);
  fft(a);
  if (eq)
    b = a;
  else
    fft(b);
  int inv_sz = inv(sz);
  for (int i = 0; i < sz; i++) {
    a[i] = mul(mul(a[i], b[i]), inv_sz);
  }
  reverse(a.begin() + 1, a.end());
  fft(a);
  a.resize(need);
  return a;
}
vector<int> square(vector<int> a) { return multiply(a, a, 1); }
}  // 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);
  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;
}