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;
int n, k, tot, x, y, last;
long long ans;
const int N = 100010, mod = 998244353, G = 3, Ginv = (mod + 1) / 3;
int head[N], to[N << 1], nt[N << 1], r[N << 2], siz[N], jc[N], inv[N], f[N],
    sum[N], val1[N], val2[N];
inline int read() {
  int res = 0;
  char ch = getchar();
  bool XX = false;
  for (; !isdigit(ch); ch = getchar()) (ch == '-') && (XX = true);
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return XX ? -res : res;
}
inline int W(int x) { return x >= mod ? x - mod : x; }
inline void add(int f, int t) {
  to[++tot] = t;
  nt[tot] = head[f];
  head[f] = tot;
}
inline int ksm(int a, int b, long long mod) {
  int res = 1;
  for (; b; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) res = (long long)res * a % mod;
  return res;
}
inline void NTT(int *A, int lim, int opt) {
  if (last != lim) {
    last = lim;
    for (int i = 0; i < lim; ++i)
      r[i] = (r[i >> 1] >> 1) | (i & 1 ? (lim >> 1) : 0);
  }
  for (int i = 0; i < lim; ++i)
    if (i < r[i]) swap(A[i], A[r[i]]);
  int len, wn, w, x, y;
  for (int mid = 1; mid < lim; mid <<= 1) {
    len = mid << 1;
    wn = ksm(opt == 1 ? G : Ginv, (mod - 1) / len, mod);
    for (int j = 0; j < lim; j += len) {
      w = 1;
      for (int k = j; k < j + mid; ++k, w = (long long)w * wn % mod) {
        x = A[k];
        y = (long long)A[k + mid] * w % mod;
        A[k] = W(x + y);
        A[k + mid] = W(x - y + mod);
      }
    }
  }
  if (opt == 1) return;
  int ni = ksm(lim, mod - 2, mod);
  for (int i = 0; i < lim; ++i) A[i] = (long long)A[i] * ni % mod;
}
int A[N << 2], B[N << 2];
struct DXS {
  int siz;
  vector<int> v;
  DXS() {
    siz = 0;
    v.clear();
  }
  inline void resize(int x) {
    v.resize(x);
    siz = x;
  }
  inline friend DXS operator+(const DXS &a, const DXS &b) {
    DXS c;
    int mn = min(a.siz, b.siz), mx = max(a.siz, b.siz);
    c.siz = mx;
    c.v.resize(c.siz);
    for (int i = 0; i < mn; ++i) c.v[i] = W(a.v[i] + b.v[i]);
    if (a.siz < b.siz)
      for (int i = mn; i < mx; ++i) c.v[i] = b.v[i];
    else
      for (int i = mn; i < mx; ++i) c.v[i] = a.v[i];
    return c;
  }
  inline friend DXS operator*(const DXS &a, const DXS &b) {
    DXS c;
    int siz = 1;
    while (siz < a.siz + b.siz) siz <<= 1;
    for (int i = 0; i < a.siz; ++i) A[i] = a.v[i];
    for (int i = a.siz; i < siz; ++i) A[i] = 0;
    for (int i = 0; i < b.siz; ++i) B[i] = b.v[i];
    for (int i = b.siz; i < siz; ++i) B[i] = 0;
    NTT(A, siz, 1);
    NTT(B, siz, 1);
    for (int i = 0; i < siz; ++i) A[i] = (long long)A[i] * B[i] % mod;
    NTT(A, siz, -1);
    c.siz = a.siz + b.siz - 1;
    c.v.resize(c.siz);
    for (int i = 0; i < c.siz; ++i) c.v[i] = A[i];
    return c;
  }
};
void YYCH() {
  jc[0] = jc[1] = inv[0] = inv[1] = 1;
  for (int i = 1; i <= k; ++i) jc[i] = (long long)jc[i - 1] * i % mod;
  inv[k] = ksm(jc[k], mod - 2, mod);
  for (int i = k - 1; i >= 1; --i)
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
}
void solve(int l, int r, DXS &f, DXS &g) {
  if (l == r) {
    g.resize(1);
    g.v[0] = val1[l];
    f.resize(2);
    f.v[0] = 1;
    f.v[1] = val2[l];
    return;
  }
  int mid = (l + r) >> 1;
  DXS lf, lg, rf, rg;
  solve(l, mid, lf, lg);
  solve(mid + 1, r, rf, rg);
  f = lf * rf;
  g = (lf * rg) + (rf * lg);
}
inline int AA(int n, int m) { return (long long)jc[n] * inv[n - m] % mod; }
void dfs(int x, int fa) {
  siz[x] = 1;
  int pre = 0, son = 0;
  for (int i = head[x]; i; i = nt[i])
    if (to[i] != fa) {
      dfs(to[i], x);
      ++son;
      siz[x] += siz[to[i]];
      sum[x] = W(sum[x] + sum[to[i]]);
      (ans += (long long)pre * sum[to[i]]) %= mod;
      pre = W(pre + sum[to[i]]);
    }
  if (son) {
    DXS F, G, T;
    int cnt = 0;
    for (int i = head[x]; i; i = nt[i])
      if (to[i] != fa) val1[++cnt] = sum[to[i]], val2[cnt] = siz[to[i]];
    solve(1, cnt, F, G);
    T.resize(2);
    T.v[0] = 1;
    T.v[1] = n - siz[x];
    G = G * T;
    for (int i = 0; i <= min(k, son); ++i) {
      (ans += (long long)AA(k, i) * G.v[i]) %= mod;
      f[x] = ((long long)f[x] + (long long)AA(k, i) * F.v[i]) % mod;
    }
    sum[x] = W(sum[x] + f[x]);
  } else
    f[x] = sum[x] = 1;
}
int main() {
  cin >> n >> k;
  if (k == 1) return printf("%lld", (long long)n * (n - 1) / 2 % mod) == 2333;
  YYCH();
  for (int i = 1; i < n; ++i) x = read(), y = read(), add(x, y), add(y, x);
  dfs(1, 0);
  cout << ans;
  return 0;
}