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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXPATH = 100000;
const int MOD = 998244353;
const int PRIMROOT = 3;
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
struct NTT {
  void _init(int n, int &nlog, int &g, vector<int> &w) {
    assert((MOD - 1) % n == 0);
    g = pw(PRIMROOT, (MOD - 1) / n);
    nlog = 0;
    while ((1 << nlog) < n) ++nlog;
    if ((1 << nlog) != n) nlog = -1;
    w = vector<int>(n);
    w[0] = 1;
    for (int i = (1); i < (n); ++i) w[i] = (long long)w[i - 1] * g % MOD;
  }
  int fftn, fftnlog;
  int fftg;
  vector<int> fftw;
  void initfft(int n) {
    fftn = n, _init(fftn, fftnlog, fftg, fftw);
    assert(fftnlog != -1);
  }
  void fft(int *a, int n, bool inv) {
    if (n != fftn) initfft(n);
    for (int i = 1, j = n >> 1, k, l = j; i < n; j ^= k, ++i) {
      if (i < j) swap(a[i], a[j]);
      for (k = l; k & j; j ^= k, k >>= 1)
        ;
    }
    int *l, *r, *w;
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    for (int hlen = 1, step = n >> 1; hlen < n; hlen <<= 1, step >>= 1) {
      for (int i = 0; i < n; i += (hlen << 1)) {
        l = a + i, r = l + hlen, w = fftw.data();
        for (int off = (0); off < (hlen); ++off) {
          int v = (long long)(*r) * (*w) % MOD;
          *r = (*l) - v;
          if (*r < 0) *r += MOD;
          *l = (*l) + v;
          if (*l >= MOD) *l -= MOD;
          ++l, ++r, w += step;
        }
      }
    }
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    if (inv) {
      int mlt = pw(n, MOD - 2);
      for (int i = (0); i < (n); ++i) a[i] = (long long)a[i] * mlt % MOD;
    }
  }
  void mult(int *a, int na, int *b, int nb, int *c, int nc) {
    int sz = 1;
    while (sz < na + nb - 1) sz *= 2;
    vector<int> A(sz, 0), B(sz, 0);
    for (int i = (0); i < (na); ++i) A[i] = a[i];
    for (int i = (0); i < (nb); ++i) B[i] = b[i];
    fft(A.data(), sz, false);
    fft(B.data(), sz, false);
    for (int i = (0); i < (sz); ++i) A[i] = (long long)A[i] * B[i] % MOD;
    fft(A.data(), sz, true);
    for (int i = (0); i < (nc); ++i) c[i] = i < sz ? A[i] : 0;
  }
};
int n, npath;
vector<int> adj[MAXN];
int fac[MAXPATH + 1];
int inv[MAXPATH + 1];
int ifac[MAXPATH + 1];
int sz[MAXN];
int waysdown[MAXN];
int waysup[MAXN];
void dfsinit(int at, int par) {
  sz[at] = 1;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    dfsinit(to, at);
    sz[at] += sz[to];
  }
}
pair<int, int> opt[MAXN];
int nopt;
NTT ntt;
vector<int> rec(int l, int r) {
  if (l == r) {
    vector<int> ret;
    ret.push_back(1);
    ret.push_back(opt[l].first);
    return ret;
  }
  int m = l + (r - l) / 2;
  vector<int> a = rec(l, m), b = rec(m + 1, r);
  vector<int> c;
  c.resize(((int)(a).size()) + ((int)(b).size()) - 1);
  ntt.mult(a.data(), ((int)(a).size()), b.data(), ((int)(b).size()), c.data(),
           ((int)(c).size()));
  return c;
}
void dfsways(int at, int par) {
  nopt = 0;
  if (par != -1) opt[nopt++] = make_pair(n - sz[at], par);
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    opt[nopt++] = make_pair(sz[to], to);
  }
  sort(opt, opt + nopt);
  vector<int> pol = rec(0, nopt - 1);
  assert(((int)(pol).size()) == nopt + 1);
  int ways = -1;
  for (int i = (0); i < (nopt); ++i) {
    if (i == 0 || opt[i - 1].first != opt[i].first) {
      int a = opt[i].first, ainv = pw(a, MOD - 2);
      vector<int> cpol(nopt, 0);
      int carry = pol[nopt];
      for (int i = nopt - 1; i >= 0; --i) {
        cpol[i] = (long long)carry * ainv % MOD;
        carry = (pol[i] + MOD - cpol[i]) % MOD;
      }
      assert(carry == 0);
      ways = 0;
      for (int k = (0); k < (((int)(cpol).size())); ++k)
        if (k <= npath)
          ways =
              (ways + (long long)cpol[k] * fac[npath] % MOD * ifac[npath - k]) %
              MOD;
    }
    if (opt[i].second == par)
      waysdown[at] = ways;
    else
      waysup[opt[i].second] = ways;
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    dfsways(to, at);
    waysdown[at] = (waysdown[at] + waysdown[to]) % MOD;
  }
}
int dfscalc(int at, int par) {
  int ret = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    ret = (ret + dfscalc(to, at)) % MOD;
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    ret = (ret + (long long)waysup[to] * waysdown[to]) % MOD;
  }
  int sum = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    ret = (ret + (long long)sum * waysdown[to]) % MOD;
    sum = (sum + waysdown[to]) % MOD;
  }
  return ret;
}
int solve() {
  if (npath == 1) return (long long)n * (n - 1) / 2 % MOD;
  if (n == 1) return 0;
  inv[1] = 1;
  for (int i = (2); i <= (npath); ++i)
    inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
  fac[0] = 1;
  for (int i = (1); i <= (npath); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  ifac[0] = 1;
  for (int i = (1); i <= (npath); ++i)
    ifac[i] = (long long)ifac[i - 1] * inv[i] % MOD;
  dfsinit(0, -1);
  dfsways(0, -1);
  return dfscalc(0, -1);
}
void run() {
  scanf("%d%d", &n, &npath);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    adj[a].push_back(b), adj[b].push_back(a);
  }
  printf("%d\n", solve());
}
void stress1() {
  n = MAXN, npath = MAXN;
  for (int i = (0); i < (n); ++i) adj[i].clear();
  int at = 1;
  for (int len = 1; at < n; ++len) {
    int clen = min(len, n - at);
    int prv = 0;
    for (int i = (0); i < (clen); ++i) {
      adj[prv].push_back(at);
      adj[at].push_back(prv);
      prv = at;
      ++at;
    }
  }
  printf("%d\n", solve());
}
void stress2() {
  n = MAXN, npath = MAXN;
  for (int i = (0); i < (n); ++i) adj[i].clear();
  int at = 1;
  while (at < n) {
    int clen = 1;
    int prv = 0;
    for (int i = (0); i < (clen); ++i) {
      adj[prv].push_back(at);
      adj[at].push_back(prv);
      prv = at;
      ++at;
    }
  }
  printf("%d\n", solve());
}
int main() {
  run();
  return 0;
}