N 頂点からなる木が与えられます。木の各頂点には 1 から N の番号が割り振られています。また、N−1 本の辺のうち、 i\ (= 1, 2, ..., N-1) 本目の辺は頂点 u_i と頂点 v_i とを結んでいます。
この木の K 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラフも頂点を共有しないものの個数を求めるプログラムを作成してください。ただし答えがとても大きくなることがあるため、998244353 で割ったあまりを答えてください。
なお、K 個の部分グラフからなる集合が同一のものは、K 個の部分グラフの順序が異なるものも同一視するものとします。
N K u_1 v_1 : u_{N-1} v_{N-1}
答えを表す整数を一行に出力してください。998244353 で割ったあまりを出力することに注意してください。
3 2 1 2 1 3
5
以下の 5 通りがあります:
4 4 1 2 1 3 1 4
1
( \{ 1 \}, \{ 2 \}, \{ 3 \}, \{ 4 \} ) の 1 通りしかありません。
7 4 1 7 2 1 7 4 3 4 5 7 6 3
166