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>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
inline int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') ch = getchar(), f = -1;
  while (isdigit(ch)) s = s * 10 + ch - '0', ch = getchar();
  return ~f ? s : -s;
}
const int maxn = (1 << 18) + 20;
const int MAX = 1 << 18;
const int mod = 998244353;
inline int power(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (long long)ans * a % mod;
    b >>= 1;
    a = (long long)a * a % mod;
  }
  return ans;
}
int jc[maxn], jcn[maxn], inv[maxn], W[maxn];
inline void prepare() {
  jc[0] = jc[1] = jcn[0] = jcn[1] = inv[1] = 1;
  for (int i = (2), _end_ = (MAX); i <= _end_; i++)
    jc[i] = (long long)i * jc[i - 1] % mod,
    inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod,
    jcn[i] = (long long)jcn[i - 1] * inv[i] % mod;
  W[0] = 1;
  W[1] = power(3, (mod - 1) / MAX);
  for (int i = (2), _end_ = (MAX - 1); i <= _end_; i++)
    W[i] = (long long)W[i - 1] * W[1] % mod;
}
inline int C(int n, int m) {
  return 1ll * jc[n] * jcn[m] % mod * jcn[n - m] % mod;
}
inline void FFT(vector<int> &p, int n, int op) {
  static int rev[maxn];
  int l = 0;
  while (1 << l < n) l++;
  for (int i = (1), _end_ = (n - 1); i <= _end_; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
  for (int i = (1), _end_ = (n - 1); i <= _end_; i++)
    if (i < rev[i]) swap(p[i], p[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0, w = (MAX / (i << 1)); j < n; j += i << 1)
      for (int k = 0; k < i; k++) {
        int x = p[j + k], y = (long long)W[w * k] * p[i + j + k] % mod;
        p[j + k] = (x + y) % mod;
        p[i + j + k] = (x - y) % mod;
      }
  if (op == -1) {
    reverse(p.begin() + 1, p.end());
    for (int i = (0), _end_ = (n - 1); i <= _end_; i++)
      p[i] = (long long)p[i] * inv[n] % mod;
  }
}
inline vector<int> operator*(vector<int> a, vector<int> b) {
  int N = 1, n = ((int)a.size()) - 1, m = ((int)b.size()) - 1;
  while (N <= ((int)a.size()) + ((int)b.size()) - 2) N <<= 1;
  a.resize(N);
  b.resize(N);
  FFT(a, N, 1);
  FFT(b, N, 1);
  for (int i = (0), _end_ = (N - 1); i <= _end_; i++)
    a[i] = (long long)a[i] * b[i] % mod;
  FFT(a, N, -1);
  a.resize(n + m + 1);
  return a;
}
int n, k;
vector<int> ed[maxn];
vector<int> f[maxn];
inline void init() {
  n = read();
  k = read();
  for (int i = (1), _end_ = (n - 1); i <= _end_; i++) {
    int u = read(), v = read();
    ed[u].push_back(v);
    ed[v].push_back(u);
  }
}
int sz[maxn];
inline void pls(int &a, int b) {
  a += b;
  a -= a >= mod ? mod : 0;
}
int ans = 0;
vector<int> operator/(vector<int> a, int y) {
  for (int i = (1), _end_ = (((int)a.size()) - 1); i <= _end_; i++) {
    a[i] = (a[i] - (long long)a[i - 1] * y) % mod;
  }
  a.resize(((int)a.size()) - 1);
  return a;
}
int fff[maxn];
void dfs(int u, int fa) {
  sort(ed[u].begin(), ed[u].end(), [](int a, int b) { return sz[a] < sz[b]; });
  int lstsz = 0;
  vector<int> F, FF = f[u] * ((vector<int>){1, n - sz[u]});
  int a = 0, up = 0;
  for (int v : ed[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int down = 0;
    if (sz[v] != lstsz) {
      F = FF / sz[v], lstsz = sz[v];
      up = 0;
      for (int j = (0), _end_ = (min(((int)F.size()) - 1, k)); j <= _end_; j++)
        up = (up + (long long)F[j] * jc[k] % mod * jcn[k - j]) % mod;
    }
    down = fff[v];
    ans = (ans + (long long)up * down) % mod;
    ans = (ans + (long long)a * fff[v]) % mod;
    a = (a + fff[v]) % mod;
  }
}
vector<int> solve(vector<int> A) {
  if (((int)A.size()) == 0) return {1};
  if (((int)A.size()) == 1) return {1, A.back()};
  vector<int> B, C;
  int len = ((int)A.size()) - 1 >> 1;
  for (int i = (0), _end_ = (((int)A.size()) - 1); i <= _end_; i++)
    if (i <= len)
      B.push_back(A[i]);
    else
      C.push_back(A[i]);
  return solve(B) * solve(C);
}
void pre_dfs(int u, int fa) {
  vector<int> now;
  for (int v : ed[u]) {
    if (v == fa) continue;
    pre_dfs(v, u);
    sz[u] += sz[v];
    now.push_back(sz[v]);
  }
  sz[u]++;
  f[u] = solve(now);
  for (int j = (0), _end_ = (min(((int)f[u].size()) - 1, k)); j <= _end_; j++)
    fff[u] = (fff[u] + (long long)f[u][j] * jc[k] % mod * jcn[k - j]) % mod;
  for (int v : ed[u])
    if (v != fa) fff[u] = (fff[u] + fff[v]) % mod;
}
inline void doing() {
  if (k == 1)
    printf("%lld\n", (long long)n * (n - 1) % mod * inv[2] % mod), exit(0);
  pre_dfs(1, 0);
  dfs(1, 0);
  ans = (ans + mod) % mod;
  printf("%d\n", ans);
}
int main() {
  prepare();
  init();
  doing();
  return 0;
}