Problem: G: Tree

problem

Given a tree consisting of N vertices. Each vertex of the tree is numbered from 1 to N. Of the N-1 edges, the i \ (= 1, 2, ..., N-1) edge connects the vertex u_i and the vertex v_i.

Write a program to find the number of K non-empty subgraph sets of this tree, each of which is concatenated and no two different subgraphs share vertices. However, the answer can be very large, so answer the remainder divided by 998244353.

Note that if the set of K subgraphs is the same, the ones with different order of K subgraphs are also equated.

Input format


N K
u_1 v_1
::
u_ {N-1} v_ {N-1}


Constraint

* 2 \ leq N \ leq 10 ^ {5}
* 1 \ leq K \ leq min (N, 300)
* 1 \ leq u_i, v_i \ leq N
* u_i \ neq v_i
* For i \ neq j (u_i, v_i) \ neq (u_j, v_j)
* All inputs are given as integers.
* The graph given is guaranteed to be a tree.



Output format

Print the integer that represents the answer on one line. Note that it prints too much divided by 998244353.

Input example 1


3 2
1 2
13


Output example 1


Five

There are five ways:

* \\ {1 \\} and \\ {2 \\}
* \\ {1 \\} and \\ {3 \\}
* \\ {2 \\} and \\ {3 \\}
* \\ {1, 2 \\} and \\ {3 \\}
* \\ {1, 3 \\} and \\ {2 \\}



Input example 2


4 4
1 2
13
14


Output example 2


1

There is only one way (\\ {1 \\}, \\ {2 \\}, \\ {3 \\}, \\ {4 \\}).

Input example 3


7 4
1 7
twenty one
7 4
3 4
5 7
6 3


Output example 3


166





Example

Input

3 2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll inf = 998244353;

vector<vector<ll>> dp0(100000+1,vector<ll>(300+2,0)),dp1(100000+1,vector<ll>(300+2,0));
vector<vector<int>> v(100000+1);
vector<int> s(100000+1,0);


void dfs(int n,int m,int K){//,vector<int>& s,vector<vector<int>>& v,vector<vector<ll>>& dp0, vector<vector<ll>>& dp1){
    dp1[n][1] = 1;
    dp0[n][0] = 1;
    s[n] = 1;
    for(auto x:v[n]) if(x!=m){
        dfs(x,n,K);//,s,v,dp0,dp1);
        vector<ll> merge0(K+2,0),merge1(K+2,0);
        for(int i=0;i<=s[n];i++) for(int j=0;j<=s[x];j++){
            if(i+j>=K+2) break;
            (merge0[i+j] += dp0[n][i]*(dp0[x][j]+dp1[x][j])%inf)%=inf;
            (merge1[i+j] += dp1[n][i]*(dp0[x][j]+dp1[x][j])%inf)%=inf;
            if(j>=1){
                (merge1[i+j-1] += dp1[n][i]*dp1[x][j]%inf)%=inf;
            }
        }
        s[n] += s[x];
        s[n] = min(s[n],K+1);
        for(int i=1;i<=K+1;i++){
            dp0[n][i] = merge0[i];
            dp1[n][i] = merge1[i];
        }
    }
}

int main(){
    int N,K;
    cin >> N >> K;
/*    vector<vector<ll>> dp0(N+1,vector<ll>(K+2,0)),dp1(N+1,vector<ll>(K+2,0));
    vector<vector<int>> v(N+1);
    vector<int> s(N+1,0);
*/    for(int i=0;i<N-1;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0,K);//,s,v,dp0,dp1);
    cout << (dp0[1][K]+dp1[1][K])%inf << endl;
}