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 maxn = 262144;
const int mod = 998244353;
const int G = 3, I = 332748118;
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
inline int dec(int a, int b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
inline int power(int a, int b) {
  int out = 1;
  while (b) {
    if (b & 1) out = mult(out, a);
    a = mult(a, a);
    b >>= 1;
  }
  return out;
}
namespace polynomial {
int R[maxn], pw[maxn], inv[maxn];
void init2() {
  for (int i = 1; i < maxn; i++)
    pw[i] = power(G, (mod - 1) / (i << 1)),
    inv[i] = power(I, (mod - 1) / (i << 1));
}
void init(int cnt) {
  for (int i = 0; i < (1 << cnt); i++)
    R[i] = (R[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
}
void ntt(vector<int> &A, int flag, int len, bool reinit = 1) {
  int tlen = 1, tcnt = 0;
  while (tlen < len) tlen <<= 1, ++tcnt;
  if (reinit) init(tcnt);
  A.resize(tlen);
  for (int i = 0; i < tlen; i++)
    if (i < R[i]) swap(A[i], A[R[i]]);
  for (int i = 1; i < tlen; i <<= 1) {
    int bas = pw[i];
    if (flag == -1) bas = inv[i];
    for (int j = 0; j < tlen; j += (i << 1)) {
      int t = 1;
      for (int k = 0; k < i; k++, t = mult(t, bas)) {
        int tx = A[j + k], ty = mult(A[i + j + k], t);
        A[j + k] = add(tx, ty);
        A[i + j + k] = dec(tx, ty);
      }
    }
  }
  if (flag == -1) {
    int I = power(tlen, mod - 2);
    for (int i = 0; i < tlen; i++) A[i] = mult(A[i], I);
  }
  A.resize(len);
}
vector<int> Mult(vector<int> A, vector<int> B, int len1, int len2) {
  A.resize(len1);
  B.resize(len2);
  int len = len1 + len2 - 1;
  int tlen = 1;
  while (tlen < len) tlen <<= 1;
  vector<int> ret;
  ret.clear();
  ret.resize(tlen);
  ntt(A, 1, tlen);
  ntt(B, 1, tlen, 0);
  for (int i = 0; i < tlen; i++) ret[i] = mult(A[i], B[i]);
  ntt(ret, -1, tlen, 0);
  ret.resize(len);
  return ret;
}
vector<int> Mult(vector<int> A, vector<int> B) {
  return Mult(A, B, A.size(), B.size());
}
vector<int> Add(vector<int> A, vector<int> B) {
  vector<int> ret;
  ret.resize(max(A.size(), B.size()));
  for (int i = 0; i < ret.size(); i++) {
    if (i < A.size()) ret[i] = A[i];
    if (i < B.size()) ret[i] = add(ret[i], B[i]);
  }
  return ret;
}
}  // namespace polynomial
using namespace polynomial;
int n, K, siz[100010], fac[100010], ans[100010], ifac[100010];
vector<int> v[100010], f[100010];
inline vector<int> solve(int l, int r, const vector<int> &t) {
  if (l == r) return vector<int>({1, t[l]});
  int mid = (l + r) >> 1;
  return Mult(solve(l, mid, t), solve(mid + 1, r, t));
}
inline vector<int> getpoly(const vector<int> &t) {
  if (!t.size()) return vector<int>({1});
  return solve(0, t.size() - 1, t);
}
int S = 0, S1 = 0, res;
void dfs(int np, int fath) {
  siz[np] = 1;
  for (int &x : v[np]) {
    if (x == fath) continue;
    dfs(x, np);
    siz[np] += siz[x];
  }
  vector<int> cur;
  for (int &x : v[np]) {
    if (x == fath) continue;
    cur.push_back(siz[x]);
  }
  f[np] = getpoly(cur);
  for (int i = 0; i < f[np].size() && i <= K; i++)
    ans[np] = add(ans[np], mult(f[np][i], mult(fac[K], ifac[K - i])));
  S = add(S, ans[np]);
  S1 = add(S1, mult(ans[np], ans[np]));
}
void dfs2(int np, int fath) {
  vector<pair<int, int> > c;
  int t = ans[np];
  for (int &x : v[np]) {
    if (x == fath) continue;
    dfs2(x, np);
    ans[np] = add(ans[np], ans[x]);
    c.push_back(make_pair(siz[x], ans[x]));
  }
  res = dec(res, mult(t, dec(ans[np], t)));
  sort(c.begin(), c.end());
  f[np].push_back(0);
  for (int i = f[np].size() - 1; i >= 1; i--)
    f[np][i] = add(f[np][i], mult(f[np][i - 1], n - siz[np]));
  int lst = -1;
  for (int i = 0; i < c.size(); i++) {
    if (!i || c[i].first != c[i - 1].first) {
      vector<int> cur(f[np].size());
      cur[0] = 1;
      for (int j = 1; j < cur.size(); j++)
        cur[j] = dec(f[np][j], mult(cur[j - 1], c[i].first));
      lst = 0;
      for (int j = 0; j < cur.size() && j <= K; j++)
        lst = add(lst, mult(cur[j], mult(fac[K], ifac[K - j])));
    }
    res = add(res, mult(lst, c[i].second));
  }
}
int main() {
  init2();
  scanf("%d%d", &n, &K);
  for (int i = 1, ti, tj; i < n; i++) {
    scanf("%d%d", &ti, &tj);
    v[ti].push_back(tj);
    v[tj].push_back(ti);
  }
  if (K == 1) {
    printf("%d\n", mult(mult(n, n - 1), (mod + 1) / 2));
    return 0;
  }
  fac[0] = 1;
  for (int i = 1; i <= 100000; i++) fac[i] = mult(fac[i - 1], i);
  ifac[100000] = power(fac[100000], mod - 2);
  for (int i = 100000 - 1; i >= 0; i--) ifac[i] = mult(ifac[i + 1], i + 1);
  dfs(1, 0);
  res = mult(dec(mult(S, S), S1), (mod + 1) / 2);
  dfs2(1, 0);
  printf("%d\n", res);
  return 0;
}