题目背景

莫言的《冰雪美人》

响起的《Promise》

昏暗的灯火

怒嚎的狂风

残破的回忆

囚禁着内心

沉入海底

步入绝望

没入寂静

只求莫再

怀念过往

徒增悲伤

题目描述

鸽子的老家是一棵 $n$ 个节点的树，节点编号为 $1\sim n$。这是鸽子三年来第一次回老家，鸽子发现树的边受了些损伤。设损伤的边集为 $S$，$P(a,b)$ 表示节点 $a,b$ 之间简单路径的边集，鸽子用下面这个函数表示树的受损程度：

$$ f(S)=\sum_{1\le a_1 < a_2 < \cdots < a_m \le n}\left[\prod_{1\le i < j\le m } \left|P(a_i,a_j)\cap S\right| \ge 1.242803739^{(m-1)(m-2)}\right] $$

鸽子会告诉你树边 $e_1,e_2,\cdots,e_{n-1}$。你需要依次求出 $f(\{e_1\}),f(\{e_1,e_2\}),\cdots,f(\{e_1,e_2,\cdots,e_{n-1}\})$，答案对 $1914270647$ 取模。

输入格式

第一行两个正整数 $n,m$。

接下来 $n-1$ 行，依次给出树边 $e_1,e_2,\cdots,e_{n-1}$。每行两个整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

输出格式

共 $n-1$ 行，每行一个整数。

样例一

input

4 2
1 2
1 3
1 4

output

3
5
6

样例二

input

8 3
1 2
3 4
5 6
2 7
3 6
2 8
2 3

output

0
6
16
28
40
50
56

样例三

见下发文件。

大样例

数据范围

所有数据满足 $1\le u,v\le n$，$2\le n\le 10^5$，$2\le m \le 10$。