odds

度度熊有一棵 $N$ 个节点 (node) 的有根树 (rooted tree)，树上的每条边 (edge) 都有一个整数的权重，对于每一个非叶的节点 (non-leaf node)，通往子节点 (child) 的所有边的权重总和为 $2 \times 10^5$。

考虑以下在树上行走的随机过程：

1. 起始位置在根节点。
2. 如果现在位置在任何一个叶节点 (leaf node) 上，则结束。
3. 令现在所在的节点通往子节点i的边为 $e_i$，其权重为 $v_i$。
4. 定义 $P(e_i)$ 为选择到边 $e_i$ 的概率，以 $P(e_i) = v_i / (2 \times 10^5)$ 的概率分布随机选择一条边，移动至对应的子节点。
5. 跳至第 2. 步骤。

接下来我们定义以下的操作：

1. 选定一个非叶节点
2. 将这个节点所有通往子节点的边的权重随意重新排序，亦即可以无限次地交换彼此之间的权重，但不能改变权重的大小。

给定一个固定的 $X$ 值，请对于每个叶节点分开考虑以下问题：

如果能进行至多 $X$ 次的操作，那到达这个叶节点的概率最大可以多大呢？

输入的第一行有一个正整数 $T$，代表接下来有几组测试数据。

对于每组测试数据：
第一行有两个整数 $N$, $X$。
接下来的 $N - 1$ 行中，每行有三个整数 $a$, $b$ 以及 $v$，代表这颗树上节点 $a$ 至节点 $b$ 有一条权重为 $v $ 的边，同时，保证 $b$ 为 $a$ 的子节点。
节点的编号由 $0$ 至 $N - 1$，节点 $0$ 为树根。

* $2 \le N \le 10^5$
* $0 \le X \le N$
* $0 \le a, b < N$
* $0 \le v \le $ $2 \times 10^5$
* 节点 $b$ 为 $a$ 的子节点
* 对于非叶节点，其所有通往子节点的边的权重总合為 $2 \times 10^5$
* $1 \le T \le 21$
* 至多 $2$ 组测试数据中的 $N > 2000$

对于每一组测试数据，对于每一个叶节点，请依序在一行中输出一个整数 $V$，如果这个节点的答案的最简有理数为 $P / Q$，则 $V = P \times Q ^ {-1} \ mod\ 10^9 + 7$ 。
请按照节点编号的顺序由小至大输出。
两组测试数据间请不要输出多余的空白行。

在本题中，对于正整数 $Q$，定义$Q^{-1}$ 的值为一正整数 $Q'$ 滿足 $Q'< 10^9 + 7$ 且 $Q$$\times Q'$$mod$ $10^9 + 7$ = $1$。

1
11 2
0 1 100
0 2 199700
0 3 200
1 4 120000
1 5 80000
3 6 100000
3 7 100000
7 8 90000
7 9 90000
7 10 20000

714500006
628700005
628700005
357250003
110762501
110762501
110762501

2018 “百度之星”程序设计大赛 - 初赛（B）