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 <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const long long P = 998244353;
const int maxn = 1 << 18;
void add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
long long deg(long long x, long long d) {
  d %= P - 1;
  if (d < 0) d += P - 1;
  long long y = 1;
  while (d) {
    if (d & 1) (y *= x) %= P;
    (x *= x) %= P;
    d /= 2;
  }
  return y;
}
int bitrev(int n, int i) {
  for (int l = 1, r = n / 2; l < r; l <<= 1, r >>= 1) {
    if (((i / l) & 1) != ((i / r) & 1)) i ^= l | r;
  }
  return i;
}
long long omega = 0;
long long r[20][2 * maxn];
void fft(int n, int *a, bool inv) {
  for (int i = 0; i < (int)(n); ++i) {
    int j = bitrev(n, i);
    if (i < j) swap(a[i], a[j]);
  }
  for (int l = 1, q = 0; l < n; l *= 2, ++q) {
    for (int i = 0; i < n; i += 2 * l) {
      for (int j = 0; j < (int)(l); ++j) {
        int x = a[i + j], y = a[i + l + j];
        int z = 1LL * y * r[q][inv ? (2 << q) - j : j] % P;
        a[i + j] = (x + z) % P;
        a[i + l + j] = (x - z) % P;
      }
    }
  }
  if (inv) {
    int z = deg(n, -1);
    for (int i = 0; i < (int)(n); ++i) a[i] = 1LL * a[i] * z % P;
  }
}
int pa[maxn], push_back[maxn], res[maxn];
void sum(const vector<int> &a, const vector<int> &b, vector<int> &c) {
  int n = max(a.size(), b.size());
  c.assign(n, 0);
  for (int i = 0; i < (int)(n); ++i) {
    if (i < a.size()) add(c[i], a[i]);
    if (i < b.size()) add(c[i], b[i]);
  }
}
void prod(const vector<int> &a, const vector<int> &b, vector<int> &c) {
  if (a.empty() || b.empty()) {
    c.clear();
    return;
  }
  int n = a.size(), m = b.size();
  c.assign(n + m - 1, 0);
  int N = 1;
  while (N < n + m) N *= 2;
  for (int i = 0; i < (int)(N); ++i) pa[i] = i < n ? a[i] : 0;
  fft(N, pa, false);
  for (int i = 0; i < (int)(N); ++i) push_back[i] = i < m ? b[i] : 0;
  fft(N, push_back, false);
  for (int i = 0; i < (int)(N); ++i) pa[i] = 1LL * pa[i] * push_back[i] % P;
  fft(N, pa, true);
  for (int i = 0; i < (int)(n + m - 1); ++i)
    if ((c[i] = pa[i]) < 0) c[i] += P;
}
void dncprod(const vector<vector<int> > &muls, const vector<int> &x, int l,
             int r, vector<int> &s0, vector<int> &s1) {
  if (l == r) {
    s0 = {1};
    s1 = {};
    return;
  }
  if (r - l == 1) {
    s0 = muls[l];
    s1 = {x[l]};
    return;
  }
  int m = (l + r) / 2;
  vector<int> ls0, ls1, rs0, rs1;
  dncprod(muls, x, l, m, ls0, ls1);
  dncprod(muls, x, m, r, rs0, rs1);
  prod(ls0, rs0, s0);
  vector<int> h1, h2;
  prod(ls0, rs1, h1);
  prod(ls1, rs0, h2);
  sum(h1, h2, s1);
}
vector<int> dprod(const vector<int> &a, const vector<int> &b) {
  if (a.empty() || b.empty()) return {};
  vector<int> c(a.size() + b.size() - 1);
  for (int i = 0; i < (int)(a.size()); ++i)
    for (int j = 0; j < (int)(b.size()); ++j)
      add(c[i + j], 1LL * a[i] * b[j] % P);
  return c;
}
int n, k;
vector<int> e[maxn];
int down[maxn], sdown[maxn];
int w[maxn];
long long fact[maxn], tcaf[maxn];
int total = 0;
void dfs(int v, int par) {
  vector<vector<int> > muls;
  vector<int> x;
  w[v] = 1;
  long long sd = 0;
  for (int u : e[v]) {
    if (u == par) continue;
    dfs(u, v);
    w[v] += w[u];
    muls.push_back({1, w[u]});
    x.push_back(sdown[u]);
    add(total, 1LL * sdown[v] * sdown[u] % P);
    add(sdown[v], sdown[u]);
  }
  vector<int> p, q;
  dncprod(muls, x, 0, muls.size(), p, q);
  for (int i = 0; i < (int)(p.size()); ++i) {
    if (i > k) break;
    add(down[v], 1LL * p[i] * fact[k] % P * tcaf[k - i] % P);
  }
  add(sdown[v], down[v]);
  q = dprod(q, {1, n - w[v]});
  for (int i = 0; i < (int)(q.size()); ++i) {
    if (i > k) break;
    add(total, 1LL * q[i] * fact[k] % P * tcaf[k - i] % P);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  while (1) {
    if (deg(omega, maxn) == 1 && deg(omega, maxn / 2) != 1) break;
    ++omega;
  }
  for (int i = 0; i < (int)(17); ++i) {
    r[i][0] = 1;
    long long w0 = deg(omega, maxn >> (i + 1));
    for (int j = 0; j < (int)(1 << (i + 1)); ++j)
      r[i][j + 1] = 1LL * r[i][j] * w0 % P;
  }
  cin >> n >> k;
  fact[0] = 1;
  for (int i = 1; i <= (int)(k); ++i) fact[i] = i * fact[i - 1] % P;
  for (int i = 0; i < (int)(k + 1); ++i) tcaf[i] = deg(fact[i], -1);
  for (int i = 0; i < (int)(n - 1); ++i) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  if (k > 1)
    dfs(0, -1);
  else
    total = 1LL * n * (n - 1) / 2 % P;
  cout << total << '\n';
  return 0;
}