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;
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 100007, __ = 266667, mo = 998244353, gmo = 3, igmo = 332748118;
template <typename T1, typename T2>
inline T1 ad(T1 &a, T2 b) {
  return a = a + b >= mo ? a + b - mo : a + b;
}
template <typename T1, typename T2>
inline T1 dl(T1 &a, T2 b) {
  return a = a >= b ? a - b : a - b + mo;
}
template <typename T1, typename T2>
inline T1 add(T1 a, T2 b) {
  return a + b >= mo ? a + b - mo : a + b;
}
template <typename T1, typename T2>
inline T1 del(T1 a, T2 b) {
  return a >= b ? a - b : a - b + mo;
}
long long powa(long long a, long long t) {
  long long b = 1;
  a = (a + mo) % mo;
  while (t) {
    if (t & 1) b = b * a % mo;
    a = a * a % mo, t >>= 1;
  }
  return b;
}
inline long long inva(long long a) { return powa(a, mo - 2); }
long long jc[__], rjc[__];
void fuck(int n = __ - 1) {
  jc[0] = jc[1] = rjc[0] = 1;
  for (int i = 2; i <= n; i++) jc[i] = jc[i - 1] * i % mo;
  rjc[n] = inva(jc[n]);
  for (int i = n - 1; i >= 1; i--) rjc[i] = rjc[i + 1] * (1ll + i) % mo;
}
inline long long A(int n, int m) {
  if (n < m || n < 0 || m < 0) return 0;
  return jc[n] * rjc[n - m] % mo;
}
int rev[__];
int nttmake(int n) {
  int nn = 1, lg = 0;
  while (nn <= n) nn <<= 1, lg++;
  rev[0] = 0;
  for (int i = 1; i < nn; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  return nn;
}
void ntt(long long a[], int nn, int dir) {
  for (int i = 0; i < nn; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 1; i < nn; i <<= 1)
    for (int g = powa(dir > 0 ? gmo : igmo, (mo - 1) / (i + i)), j = 0; j < nn;
         j += i + i)
      for (int k = 0, x, y, ig = 1; k < i; k++, ig = 1ll * ig * g % mo)
        x = a[j + k], y = a[j + k + i] * ig % mo, a[j + k] = add(x, y),
        a[j + k + i] = del(x, y);
  if (dir < 0)
    for (int i = 0, x = inva(nn); i < nn; i++) a[i] = a[i] * x % mo;
}
void ntt(vector<long long> &a, int nn, int dir) {
  static long long pa[__];
  a.resize(nn);
  for (int i = 0; i < nn; i++) pa[i] = a[i];
  ntt(pa, nn, dir);
  for (int i = 0; i < nn; i++) a[i] = pa[i];
}
int to[__], ne[__], he[_] = {0}, ecnt = 1;
inline void adde(int a, int b) {
  to[++ecnt] = b, ne[ecnt] = he[a], he[a] = ecnt;
}
inline void addde(int a, int b) { adde(a, b), adde(b, a); }
int n, m, sz[_] = {0};
long long f[_] = {0}, sf[_] = {0}, sumf = 0, ans = 0;
int stk[_] = {0}, top = 0;
pair<vector<long long>, vector<long long> > make(int l, int r, int opt) {
  if (l == r) {
    if (opt == 0)
      return make_pair(vector<long long>{1, sz[stk[l]]}, vector<long long>{});
    if (l == top)
      return make_pair(vector<long long>{0},
                       vector<long long>{1, n - sz[stk[l]]});
    return make_pair(vector<long long>{add(f[stk[l]], sf[stk[l]])},
                     vector<long long>{1, sz[stk[l]]});
  }
  int mid = (l + r) >> 1, len = r - l + 1;
  pair<vector<long long>, vector<long long> > ll = make(l, mid, opt),
                                              rr = make(mid + 1, r, opt);
  int nn = nttmake(len);
  if (opt == 0) {
    ntt(ll.first, nn, 1), ntt(rr.first, nn, 1);
    for (int i = 0; i < nn; i++) ll.first[i] = ll.first[i] * rr.first[i] % mo;
    ntt(ll.first, nn, -1), ll.first.resize(len + 1);
  } else {
    ntt(ll.first, nn, 1), ntt(rr.first, nn, 1);
    ntt(ll.second, nn, 1), ntt(rr.second, nn, 1);
    for (int i = 0; i < nn; i++)
      ll.first[i] =
          add(ll.first[i] * rr.second[i] % mo, rr.first[i] * ll.second[i] % mo);
    for (int i = 0; i < nn; i++)
      ll.second[i] = ll.second[i] * rr.second[i] % mo;
    ntt(ll.first, nn, -1), ntt(ll.second, nn, -1);
    ll.first.resize(len + 1), ll.second.resize(len + 1);
  }
  return ll;
}
void dfs(int x, int ff) {
  sz[x] = 1;
  for (int i = he[x]; i; i = ne[i]) {
    int b = to[i];
    if (b != ff) dfs(b, x), ad(sf[x], f[b]), ad(sf[x], sf[b]), sz[x] += sz[b];
  }
  top = 0;
  for (int i = he[x]; i; i = ne[i])
    if (to[i] != ff) stk[++top] = to[i];
  if (top > 0) {
    vector<long long> ma = make(1, top, 0).first;
    for (int i = 0; i < (int)ma.size() && i <= m; i++)
      ad(f[x], A(m, i) * ma[i] % mo);
    stk[++top] = x, ma = make(1, top, 1).first;
    for (int i = 0; i < (int)ma.size() && i <= m; i++)
      ad(ans, A(m, i) * ma[i] % mo);
  } else
    f[x] = 1;
  ad(ans, sumf * f[x] % mo), dl(ans, f[x] * sf[x] % mo);
  ad(sumf, f[x]);
}
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  fuck();
  n = ty(), m = ty();
  for (int i = 1, a, b; i < n; i++) a = ty(), b = ty(), addde(a, b);
  if (m == 1) {
    cout << 1ll * n * (n - 1) / 2 % mo << lf;
    return 0;
  }
  dfs(1, 0), cout << ans << lf;
  return 0;
}