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 gbd_ns {
template <typename C>
struct is_iterable {
  template <class T>
  static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T>
ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <bool B, typename T = void>
using eit = typename enable_if<B, T>::type;
template <class T>
struct _gbd3C;
template <class T>
ostream &_gbd3(ostream &os, const T &x) {
  return _gbd3C<T>::call(os, x);
}
template <class T>
struct _gbd3C {
  template <class U = T>
  static ostream &call(ostream &os, eit<is_iterable<U>::value, const T> &V) {
    os << "{";
    bool ff = 0;
    for (const auto &E : V) _gbd3<decltype(E)>(ff ? os << "," : os, E), ff = 1;
    return os << "}";
  }
  template <class U = T>
  static ostream &call(ostream &os,
                       eit<is_iterable<U>::neg_value, const T> &x) {
    return os << x;
  }
};
template <>
struct _gbd3C<string> {
  static ostream &call(ostream &os, const string &s) {
    return os << '"' << s << '"';
  }
};
template <>
struct _gbd3C<char *> {
  static ostream &call(ostream &os, char *const &s) {
    return os << '"' << s << '"';
  }
};
template <class S, class T>
struct _gbd3C<pair<S, T> > {
  static ostream &call(ostream &os, const pair<S, T> &p) {
    _gbd3(os << '(', p.first);
    _gbd3(os << ',', p.second);
    return os << ')';
  }
};
template <class T, typename... Args>
ostream &_gbd2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args);
ostream &_gbd2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
ostream &_gbd2(ostream &os, vector<string>::iterator nm, const char *x,
               Args &&...args) {
  return _gbd2(os << "  " << x, nm + 1, args...);
}
template <class T, typename... Args>
ostream &_gbd2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args) {
  return _gbd2(_gbd3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(') ++dep;
    if (c == ')') --dep;
  }
  return Z;
}
template <typename... Args>
ostream &_gbd1(int ln, const string &nm, Args &&...args) {
  auto nms = split(nm);
  _gbd2(cerr << "L" << ln << ":", nms.begin(), args...);
  return cerr << endl;
}
}  // namespace gbd_ns
inline void nop() {}
const int e3 = 1000;
const int e6 = e3 * e3;
const int e9 = e6 * e3;
const long double tau = 2 * acosl(-1);
typedef long double ld;
const ld eps = (ld)1e-8;
const int inf = e9 + 99;
const long long linf = 1LL * e9 * e9 + 99;
const int P = 998244353;
void add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
unsigned long long powq_ull(unsigned long long x, unsigned long long e,
                            unsigned long long p) {
  if (!e) return 1;
  if (e & 1) return x * powq_ull(x, e - 1, p) % p;
  x = powq_ull(x, e >> 1, p);
  return x * x % p;
}
const unsigned long long PP = (119ULL << 23) + 1;
const int AA = 119;
const unsigned long long ROOT = 3;
const unsigned long long INV_ROOT = 332748118;
const unsigned long long TWO_INV = 499122177;
vector<unsigned long long> fft(const vector<unsigned long long> &input,
                               const bool inv = 0) {
  const unsigned long long P = PP;
  const int A = AA;
  const unsigned long long RT = ROOT;
  const unsigned long long IRT = INV_ROOT;
  const unsigned long long I2 = TWO_INV;
  const int N = (int)input.size();
  vector<unsigned long long> arr(input);
  for (unsigned long long &x : arr) x %= P;
  for (int half = inv ? 1 : N / 2; 1 <= half && half < N;
       inv ? half <<= 1 : half >>= 1) {
    unsigned long long wm = inv ? IRT : RT;
    wm = powq_ull(wm, A, P);
    for (int ord = int((P - 1) / A); ord > 2 * half; ord >>= 1)
      wm = (wm * wm) % P;
    for (int st = 0; st < N; st += 2 * half) {
      unsigned long long w = 1;
      for (int j = st; j < st + half; ++j) {
        if (inv) arr[j + half] = arr[j + half] * w % P;
        unsigned long long a = arr[j], b = arr[j + half];
        arr[j] = a + b;
        if (arr[j] >= P) arr[j] -= P;
        arr[j + half] = a + P - b;
        if (arr[j + half] >= P) arr[j + half] -= P;
        if (!inv) arr[j + half] = arr[j + half] * w % P;
        w = (w * wm) % P;
      }
    }
  }
  if (inv) {
    unsigned long long size_inv = 1;
    for (int sz = 2; sz <= N; sz <<= 1) size_inv = (size_inv * I2) % P;
    for (unsigned long long &x : arr) x = (x * size_inv) % P;
  }
  return arr;
}
vector<int> mulfst(const vector<int> &A, const vector<int> &B) {
  int m = (int((A).size())), n = (int((B).size()));
  int w = m + n - 1;
  for (; w & (w - 1);) ++w;
  vector<unsigned long long> AA(w, 0), BB(w, 0);
  for (int i = 0; i < m; i++) AA[i] = A[i];
  for (int i = 0; i < n; i++) BB[i] = B[i];
  AA = fft(AA);
  BB = fft(BB);
  for (int i = 0; i < w; i++) AA[i] *= BB[i];
  AA = fft(AA, 1);
  for (; (int((AA).size())) > m + n - 1;) assert(!AA.back()), AA.pop_back();
  vector<int> Z;
  for (unsigned long long x : AA) Z.push_back((int)x);
  return Z;
}
vector<int> mulslo(const vector<int> &A, const vector<int> &B) {
  int n = (int((A).size())), m = (int((B).size()));
  int w = m + n - 1;
  vector<int> Z(w, 0);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) add(Z[i + j], int(1LL * A[i] * B[j] % P));
  return Z;
}
const int N = 100 << 10;
int n, k;
set<int> adj[N];
int p[N], sz[N];
int nn;
int dfs_sz(int u, int _p = -1) {
  p[u] = _p;
  sz[u] = 1;
  for (int v : adj[u])
    if (v != _p) sz[u] += dfs_sz(v, u);
  if (!~_p) nn = sz[u];
  return sz[u];
}
int siz(int u, int _p) {
  if (p[u] == _p) return sz[u];
  assert(p[_p] == u);
  return nn - sz[_p];
}
vector<int> ml(const vector<int> &szs, int l, int r) {
  if (l == r) return {1, szs[l]};
  int m = (l + r) >> 1;
  return mulfst(ml(szs, l, m), ml(szs, m + 1, r));
}
int ff(int x) {
  if (!x) return 1;
  static bool seen[N];
  static int dp[N];
  bool &sn = seen[x];
  int &ans = dp[x];
  if (sn) return ans;
  sn = 1;
  return ans = int(1LL * ff(x - 1) * x % P);
}
int iff(int x) {
  if (x == N - 3) return (int)powq_ull(ff(x), P - 2, P);
  static bool seen[N];
  static int dp[N];
  bool &sn = seen[x];
  int &ans = dp[x];
  if (sn) return ans;
  sn = 1;
  return ans = int(1LL * iff(x + 1) * (x + 1) % P);
}
int slow_eval(const vector<int> &p, int x) {
  int Z = 0;
  int qq = 0;
  for (int i = 0; i < (int((p).size())); i++) {
    qq = int((p[i] + P - 1LL * qq * x % P) % P);
    int fxqq = int(1LL * qq * ff(k) % P * iff(k - i) % P);
    add(Z, fxqq);
  }
  return Z;
}
map<int, int> WW[N];
int RR[N];
void solve(int u) {
  vector<int> sizs;
  for (int v : adj[u]) sizs.push_back(siz(v, u));
  vector<int> poly = ml(sizs, 0, (int((sizs).size())) - 1);
  for (; (int((poly).size())) > k + 1;) poly.pop_back();
  RR[u] = 0;
  for (int x : poly) add(RR[u], x);
  sort(sizs.begin(), sizs.end());
  sizs.resize(unique(sizs.begin(), sizs.end()) - sizs.begin());
  map<int, int> edp;
  for (int x : sizs) edp[x] = slow_eval(poly, x);
  for (int v : adj[u]) {
    int zz = edp[siz(v, u)];
    WW[u][v] = zz;
  }
}
int dfs_ins(int u, int p) {
  assert(WW[u].count(p));
  int z = WW[u][p];
  for (int v : adj[u])
    if (v != p) add(z, dfs_ins(v, u));
  return z;
}
int FF;
int dfs_zz(int u, int p) {
  assert(WW[u].count(p));
  int Z = int(1LL * WW[u][p] * FF % P);
  for (int v : adj[u])
    if (v != p) add(Z, dfs_zz(v, u));
  return Z;
}
int decomp(int u) {
  dfs_sz(u);
loop:;
  for (int v : adj[u])
    if (siz(v, u) > siz(u, v)) {
      u = v;
      goto loop;
    }
  int Z = 0;
  FF = 0;
  for (int v : adj[u]) {
    add(Z, dfs_zz(v, u));
    int r = dfs_ins(v, u);
    add(FF, r);
    add(Z, int(1LL * r * WW[u][v] % P));
  }
  for (int v : adj[u]) adj[v].erase(u), add(Z, decomp(v));
  adj[u].clear();
  return Z;
}
int32_t main() {
  gbd_ns::_gbd1(343, "ff(3), ff(7), iff(3), iff(2), iff(1)", ff(3), ff(7),
                iff(3), iff(2), iff(1));
  assert(P == PP);
  scanf("%d%d", &n, &k);
  assert(k == 1 || k >= n - 1);
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].insert(v);
    adj[v].insert(u);
  }
  if (n == 1) return printf("0\n"), 0;
  if (k == 1) return printf("%d\n", int((1LL * n * (n - 1) / 2) % P)), 0;
  dfs_sz(1);
  assert(n == nn);
  for (int u = 1; u <= n; u++) solve(u);
  printf("%d\n", decomp(1));
}