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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys

def getpar(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[0] = -1
	par[p] - 1
	stack = [p]
	visited = set([p])
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			stack.append(vf)
	return par

def topological_sort_tree(E, r):
	Q = [r]
	L = []
	visited = set([r])
	while Q:
		vn = Q.pop()
		L.append(vn)
		for vf in E[vn]:
			if vf not in visited:
				visited.add(vf)
				Q.append(vf)
	return L
mod = 998244353
(N, K) = map(int, input().split())
seg = 110
lim = K + 1
M = (1 << lim * seg) - 1
segb = (1 << seg) - 1
fold = 47
tm = (1 << fold) % mod
bfilter = 0
for _ in range(lim):
	bfilter = bfilter << seg
	bfilter = bfilter | (1 << fold) - 1
cfilter = M ^ bfilter

def modulo(x):
	x = x & M
	b = x & bfilter
	c = ((x & cfilter) >> fold) * tm
	x = b + c
	b = x & bfilter
	c = ((x & cfilter) >> fold) * tm
	x = b + c
	b = x & bfilter
	c = ((x & cfilter) >> fold) * tm
	x = b + c
	return x
Edge = [[] for _ in range(N)]
D = [0] * N
for _ in range(N - 1):
	(a, b) = map(int, sys.stdin.readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)
dp1 = [1 << seg] * N
dp2 = [1] * N
for l in L[:0:-1]:
	p = P[l]
	dp1[p] = modulo(dp1[p] * ((dp1[l] >> seg) + dp1[l] + dp2[l]))
	dp2[p] = modulo(dp2[p] * (dp1[l] + dp2[l]))
res1 = dp1[0] >> K * seg & segb
res2 = dp2[0] >> K * seg & segb
print((res1 + res2) % mod)