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 <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T, class U>
inline void print(T first, U second) {
  printsp(first);
  println(second);
}
template <class T, class U, class V>
inline void print(T first, U second, V z) {
  printsp(first);
  printsp(second);
  println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
vector<int> adj[101010], child[101010], tmp;
int ans, sum[101010], n, sz[101010], N1, E, F, I;
int A[1 << 18], B[1 << 18], k, flag, tval[101010], vst[101010];
inline void add(int &u, int v) {
  u += v;
  if (u >= 998244353) u -= 998244353;
}
inline int mul(int a, int b) {
  return (int)((long long)a * b % 998244353);
  unsigned long long first = (long long)a * b;
  unsigned xh = (unsigned)(first >> 32), xl = (unsigned)first, d, m;
  asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(998244353));
  return m;
}
void fft(int *A, int P, int pw) {
  for (int m = N1, h; h = m >> 1, m >= 2; pw = (long long)pw * pw % P, m = h) {
    for (int i = 0, w = 1; i < h; i++, w = (long long)w * pw % P) {
      for (int j = i; j < N1; j += m) {
        int k = j + h, first = A[j] + 998244353 - A[k];
        if (first >= 998244353) first -= 998244353;
        A[j] += A[k] - 998244353;
        A[k] = mul(first, w);
        if (A[j] < 0) A[j] += 998244353;
      }
    }
  }
  for (int i = 0, j = 1; j < N1 - 1; j++) {
    for (int k = N1 / 2; k > (i ^= k); k >>= 1)
      ;
    if (i > j) swap(A[i], A[j]);
  }
}
vector<int> multiply(const vector<int> &a, const vector<int> &b) {
  int n = a.size() + b.size() - 1;
  for (N1 = 1; N1 < n; N1 <<= 1)
    ;
  for (int i = 0; i < a.size(); i++) A[i] = a[i];
  for (int i = a.size(); i < N1; i++) A[i] = 0;
  for (int i = 0; i < b.size(); i++) B[i] = b[i];
  for (int i = b.size(); i < N1; i++) B[i] = 0;
  E = power(3, (998244353 - 1) / N1, 998244353);
  F = power(E, 998244353 - 2, 998244353);
  I = power(N1, 998244353 - 2, 998244353);
  fft(A, 998244353, E);
  fft(B, 998244353, E);
  for (int i = 0; i < N1; i++) A[i] = (long long)A[i] * B[i] % 998244353;
  fft(A, 998244353, F);
  vector<int> c(n);
  for (int i = 0; i < n; i++) c[i] = (long long)A[i] * I % 998244353;
  return c;
}
vector<int> calc(int st, int ed) {
  if (st == ed) return {1};
  if (st + 1 == ed) return {1, sz[tmp[st]]};
  return multiply(calc(st, ed + st >> 1), calc(st + ed >> 1, ed));
}
void dfs(int u, int pa = -1) {
  sz[u] = 1;
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == pa) continue;
    dfs(v, u);
    child[u].push_back(v);
    sz[u] += sz[v];
    add(ans, mul(sum[u], sum[v]));
    add(sum[u], sum[v]);
  }
  tmp = child[u];
  vector<int> res = calc(0, tmp.size());
  int mid = 1, val = 0;
  for (int i = 0, ed = min(k, (int)res.size() - 1); i <= ed; i++) {
    add(val, mul(mid, res[i]));
    mid = mul(mid, k - i);
  }
  add(sum[u], val);
  if (pa != -1) res = multiply(res, (vector<int>){1, n - sz[u]});
  ++flag;
  for (int i = 0; i < child[u].size(); i++) {
    int v = child[u][i], a = sz[v];
    int &m = tval[a];
    if (vst[a] != flag) {
      vst[a] = flag;
      int cur = 0, b = 1;
      m = 0;
      for (int j = 0, ed = min(k, (int)res.size() - 1); j <= ed; j++) {
        cur = mul(cur, a);
        cur = (res[j] - cur + 998244353) % 998244353;
        add(m, mul(b, cur));
        b = mul(b, k - j);
      }
    }
    add(ans, mul(m, sum[v]));
  }
}
int main() {
  int u, v;
  gn(n, k);
  for (int i = 1; i < n; i++) {
    gn(u, v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if (k == 1) {
    println((long long)n * (n - 1) / 2 % 998244353);
    return 0;
  }
  dfs(1);
  println(ans);
  return 0;
}