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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define MOD 998244353
#define SIZE 100005

enum Type{
	USE,
	NOT,
};

ll N,K;
ll dp[SIZE][305][2],work[305][2];
ll num_nodes[SIZE];
vector<int> G[SIZE];


void dfs(int node_id,int parent){

	//dp[頂点番号(=k)][kの部分木の分割数][kを使用しているかどうか] = 場合の数
	dp[node_id][1][USE] = 1;
	dp[node_id][0][NOT] = 1;
	num_nodes[node_id] = 1;

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];
		if(child == parent)continue;

		dfs(child,node_id);

		for(int a = 0; a <= K; a++){
			work[a][USE] = 0;
			work[a][NOT] = 0;
		}

		for(int a = 0; a <= min(num_nodes[node_id],K+1); a++){
			for(int b = 0; b <= min(num_nodes[child],K+1-a); b++){

				work[a+b][USE] += dp[node_id][a][USE]*dp[child][b][USE];
				work[a+b][USE] %= MOD;
				work[a+b][USE] += dp[node_id][a][USE]*dp[child][b][NOT];
				work[a+b][USE] %= MOD;

				work[a+b][NOT] += dp[node_id][a][NOT]*dp[child][b][USE];
				work[a+b][NOT] %= MOD;
				work[a+b][NOT] += dp[node_id][a][NOT]*dp[child][b][NOT];
				work[a+b][NOT] %= MOD;

				if(a+b > 0){
					//node_idとchildを同時に含むグループを作る
					work[a+b-1][USE] += dp[node_id][a][USE]*dp[child][b][USE];
					work[a+b-1][USE] %= MOD;
				}
			}
		}

		num_nodes[node_id] += num_nodes[child];

		for(int a = 0; a <= min(num_nodes[node_id],K+1); a++){

			dp[node_id][a][USE] = work[a][USE];
			dp[node_id][a][NOT] = work[a][NOT];
		}
	}
}


int main(){

	scanf("%lld %lld",&N,&K);

	int from,to;
	for(int loop = 0; loop < N-1; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k <= K; k++){
			for(int p = 0; p < 2; p++){
				dp[i][k][p] = 0;
			}
		}
	}

	dfs(0,-1);

	printf("%lld\n",(dp[0][K][USE]+dp[0][K][NOT])%MOD);

	return 0;
}