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;
const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;
const int MAXS = 400007;
const int MAXL = 31;
const int MOD = 998244353;
const int RT = 3;
struct eT {
  void setd(int _u, int _v, int _l) { u = _u, v = _v, last = _l; }
  int u, v, last;
} edge[MAXN * 2];
int n, K;
int ans;
int ke, la[MAXN];
int sz[MAXN];
int dp[MAXN], cv[MAXN];
int na[MAXN], tmp[MAXN * 2], cd[MAXN];
int frac[MAXN], rf[MAXN];
int ca[MAXS], cb[MAXS], cans[MAXS], rt[MAXS];
map<int, int> mp;
void init();
void input();
void work();
int dfs(int now, int fa);
int getval(int a[], int n, int x);
void polydiv(int a[], int n, int x, int ans[]);
void fft(int ar[], int tn);
void mul(int a[], int n, int b[], int m, int ans[]);
void muldivi(int a[], int l, int r, int ans[]);
int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}
void addv(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
int dec(int x, int y) {
  x -= y;
  if (x < 0) x += MOD;
  return x;
}
void decv(int &x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}
int qpow(int a, int b) {
  long long base = a, ans = 1;
  while (b) {
    if (b & 1) (ans *= base) %= MOD;
    (base *= base) %= MOD;
    b >>= 1;
  }
  return static_cast<int>(ans);
}
int main() {
  init();
  input();
  work();
}
void init() {
  ios::sync_with_stdio(false);
  frac[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    frac[i] = frac[i - 1] * static_cast<long long>(i) % MOD;
  rf[MAXN - 1] = qpow(frac[MAXN - 1], MOD - 2);
  for (int i = MAXN - 2; i >= 0; --i)
    rf[i] = rf[i + 1] * static_cast<long long>(i + 1) % MOD;
}
void input() {
  scanf("%d%d", &n, &K);
  int u, v;
  memset(la, -1, sizeof(la));
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &u, &v);
    edge[ke].setd(u, v, la[u]);
    la[u] = ke++;
    edge[ke].setd(v, u, la[v]);
    la[v] = ke++;
  }
}
void work() {
  if (K == 1) {
    printf("%d\n", (static_cast<long long>(n) * (n - 1) >> 1) % MOD);
    return;
  }
  dfs(1, -1);
  cout << ans << endl;
}
int dfs(int now, int fa) {
  sz[now] = 1;
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ fa) sz[now] += dfs(edge[i].v, now);
  int pv = 0;
  for (int i = la[now]; ~i; i = edge[i].last) {
    if (edge[i].v ^ fa) {
      addv(ans, static_cast<long long>(pv) * dp[edge[i].v] % MOD);
      addv(pv, dp[edge[i].v]);
    }
  }
  dp[now] = pv;
  int nd = 0;
  for (int i = la[now]; ~i; i = edge[i].last)
    if (edge[i].v ^ fa) na[++nd] = sz[edge[i].v];
  na[++nd] = n - sz[now];
  muldivi(na, 1, nd, tmp);
  for (int i = 0; i <= nd; ++i) na[i] = tmp[i];
  mp.clear();
  for (int i = la[now]; ~i; i = edge[i].last) {
    if (edge[i].v ^ fa) {
      addv(ans, static_cast<long long>(dp[edge[i].v]) *
                    getval(na, nd, sz[edge[i].v]) % MOD);
    }
  }
  addv(dp[now], getval(na, nd, n - sz[now]));
  return sz[now];
}
int getval(int a[], int n, int x) {
  map<int, int>::iterator it;
  if ((it = mp.find(x)) != mp.end())
    return it->second;
  else {
    polydiv(a, n, x, cd);
    int ub = (((n - 1) < (K)) ? (n - 1) : (K)), ans = 0;
    for (int i = 0; i <= ub; ++i)
      addv(ans, static_cast<long long>(cd[i]) * rf[K - i] % MOD);
    ans = static_cast<long long>(ans) * frac[K] % MOD;
    mp[x] = ans;
    return ans;
  }
}
void polydiv(int a[], int n, int x, int ans[]) {
  for (int i = 0; i <= n; ++i) ans[i] = a[i];
  for (int i = 0; i < n; ++i)
    decv(ans[i + 1], static_cast<long long>(ans[i]) * x % MOD);
}
void fft(int ar[], int tn) {
  for (int i = 0, j = 0; i < tn; ++i) {
    if (i > j) swap(ar[i], ar[j]);
    for (int bt = tn >> 1; bt && (!((j ^= bt) & bt)); bt >>= 1)
      ;
  }
  int m, x, y;
  for (int i = 2; i <= tn; i <<= 1) {
    m = i >> 1;
    for (int j = 0; j < tn; j += i) {
      for (int k = 0; k < m; ++k) {
        x = ar[j + k],
        y = static_cast<long long>(ar[j + k + m]) * rt[tn / i * k] % MOD;
        ar[j + k] = add(x, y);
        ar[j + k + m] = dec(x, y);
      }
    }
  }
}
void mul(int a[], int n, int b[], int m, int ans[]) {
  int nm = n + m;
  int tn = 1;
  while (tn <= nm) tn <<= 1;
  for (int i = 0; i <= n; ++i) ca[i] = a[i];
  for (int i = n + 1; i < tn; ++i) ca[i] = 0;
  for (int i = 0; i <= m; ++i) cb[i] = b[i];
  for (int i = m + 1; i < tn; ++i) cb[i] = 0;
  int nrt = qpow(RT, (MOD - 1) / tn);
  rt[0] = 1;
  for (int i = 1; i < tn; ++i)
    rt[i] = static_cast<long long>(rt[i - 1]) * nrt % MOD;
  fft(ca, tn);
  fft(cb, tn);
  for (int i = 0; i < tn; ++i)
    cans[i] = static_cast<long long>(ca[i]) * cb[i] % MOD;
  reverse(rt + 1, rt + tn);
  fft(cans, tn);
  int rn = qpow(tn, MOD - 2);
  for (int i = 0; i <= nm; ++i)
    ans[i] = static_cast<long long>(cans[i]) * rn % MOD;
}
void muldivi(int a[], int l, int r, int ans[]) {
  if (l == r) {
    ans[0] = 1;
    ans[1] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  muldivi(a, l, mid, ans);
  muldivi(a, mid + 1, r, ans + ((mid - l + 1) << 1));
  mul(ans, mid - l + 1, ans + ((mid - l + 1) << 1), r - mid, ans);
}