L. Send the Fool Further! (hard)

Heidi 对你的估算感到恐惧，她认为她的朋友们不可能合作把她推向债务。她预计，实际上，每个人只会随机选择一个朋友将 Heidi 送去。（这一随机性假设意味着，她现在可以任意多次访问同一个朋友……）此外，如果一个人只与 Heidi 有一个共同朋友（即，该人在树的叶子上），那么这个人就不会把 Heidi 送回去（因此 Heidi 的旅行将在某一点结束）。 Heidi 也觉得假设她能在一天内完成所有旅行不切实际。因此，现在她假设每次她在两个朋友之间旅行时，都需要购买一张新票。她想知道：她应该预期在旅途中花费多少钱？ 值得一提的是，Heidi 知道 Jenny 至少有两个朋友。 第一行包含朋友的数量 #cf_span[n]（#cf_span[3 ≤ n ≤ 105]）。接下来的 #cf_span[n - 1] 行每行包含三个空格分隔的整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[0 ≤ u, v ≤ n - 1]，#cf_span[1 ≤ c ≤ 104]），表示 #cf_span[u] 和 #cf_span[v] 是朋友，且在 #cf_span[u] 和 #cf_span[v] 之间旅行的成本为 #cf_span[c]（每次旅行都需要支付！）。 再次保证输入的社会网络构成一棵树。 假设旅行的期望成本写成一个最简分数 #cf_span[a / b]（即，#cf_span[a] 和 #cf_span[b] 互质）。那么，Heidi 这个古怪的奶牛要求你输出 。（输出一个介于 #cf_span[0] 和 #cf_span[109 + 6] 之间的整数。） 在第一个例子中，以概率 #cf_span[1 / 2]，Heidi 会从 #cf_span[0] 去 #cf_span[1]，以概率 #cf_span[1 / 2] 她会去 #cf_span[2]。第一种情况的成本是 #cf_span[10]，第二种是 #cf_span[20]。到达 #cf_span[1] 或 #cf_span[2] 后她将停止，因为 #cf_span[1] 和 #cf_span[2] 是社交树的叶子。因此，她需要支付的期望成本是 #cf_span[10·1 / 2 + 20·1 / 2 = 15]。 在第三个例子中，期望成本是 #cf_span[81 / 5]。你应该输出 #cf_span[400000019]。 在她的旅行中，Heidi 发现了她社交网络结构的一个有趣事实。她告诉你以下内容：_你可能好奇的神秘行列式不会对你的合理解法造成奇怪的错误……_ 我们提到过 Heidi 是一只古怪的奶牛吗？ ## Input 第一行包含朋友的数量 #cf_span[n]（#cf_span[3 ≤ n ≤ 105]）。接下来的 #cf_span[n - 1] 行每行包含三个空格分隔的整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[0 ≤ u, v ≤ n - 1]，#cf_span[1 ≤ c ≤ 104]），表示 #cf_span[u] 和 #cf_span[v] 是朋友，且在 #cf_span[u] 和 #cf_span[v] 之间旅行的成本为 #cf_span[c]（每次旅行都需要支付！）。再次保证输入的社会网络构成一棵树。 ## Output 假设旅行的期望成本写成一个最简分数 #cf_span[a / b]（即，#cf_span[a] 和 #cf_span[b] 互质）。那么，Heidi 这个古怪的奶牛要求你输出 。（输出一个介于 #cf_span[0] 和 #cf_span[109 + 6] 之间的整数。） [samples] ## Note 在第一个例子中，以概率 #cf_span[1 / 2]，Heidi 会从 #cf_span[0] 去 #cf_span[1]，以概率 #cf_span[1 / 2] 她会去 #cf_span[2]。第一种情况的成本是 #cf_span[10]，第二种是 #cf_span[20]。到达 #cf_span[1] 或 #cf_span[2] 后她将停止，因为 #cf_span[1] 和 #cf_span[2] 是社交树的叶子。因此，她需要支付的期望成本是 #cf_span[10·1 / 2 + 20·1 / 2 = 15]。 在第三个例子中，期望成本是 #cf_span[81 / 5]。你应该输出 #cf_span[400000019]。 在她的旅行中，Heidi 发现了她社交网络结构的一个有趣事实。她告诉你以下内容：_你可能好奇的神秘行列式不会对你的合理解法造成奇怪的错误……_ 我们提到过 Heidi 是一只古怪的奶牛吗？

Let $ T = (V, E) $ be a tree with $ n $ nodes (friends), where each edge $ (u, v) \in E $ has a positive integer cost $ c_{uv} $. Let node $ 0 $ (Jenny) be the starting point, and assume $ \deg(0) \geq 2 $. Heidi begins at node $ 0 $. At each non-leaf node $ v \neq 0 $, she chooses uniformly at random one of its neighbors to travel to next. At a leaf node $ v \neq 0 $, the process stops. (Note: node $ 0 $ is not a leaf, by assumption.) Each traversal of an edge incurs a cost equal to its weight, and costs are accumulated additively. The process ends when Heidi first reaches a leaf node (other than possibly $ 0 $, but $ 0 $ is not a leaf). Let $ \mathbb{E} $ denote the expected total cost incurred until absorption at a leaf. Define for each node $ v \in V $, the expected cost to absorption starting from $ v $ as $ E[v] $. Then: - If $ v $ is a leaf and $ v \neq 0 $, then $ E[v] = 0 $. - If $ v = 0 $, then: $$ E[0] = \sum_{u \in N(0)} \frac{1}{\deg(0)} \left( c_{0u} + E[u] \right) $$ - For any non-leaf, non-root node $ v \neq 0 $: $$ E[v] = \sum_{u \in N(v)} \frac{1}{\deg(v)} \left( c_{vu} + E[u] \right) $$ However, note that from any non-leaf node $ v \neq 0 $, the process can return to its parent. Thus, the system of equations is **not acyclic** — we must solve a linear system over the entire tree. Let $ \mathcal{L} $ be the set of leaves excluding $ 0 $ (if $ 0 $ were a leaf, but it isn’t). For all $ v \in \mathcal{L} $, $ E[v] = 0 $. For all other nodes $ v \in V \setminus \mathcal{L} $, we have: $$ E[v] = \frac{1}{\deg(v)} \sum_{u \in N(v)} \left( c_{vu} + E[u] \right) $$ Rewriting: $$ \deg(v) \cdot E[v] - \sum_{u \in N(v)} E[u] = \sum_{u \in N(v)} c_{vu} $$ This yields a system of $ n - |\mathcal{L}| $ linear equations in variables $ E[v] $ for $ v \notin \mathcal{L} $, with $ E[v] = 0 $ for $ v \in \mathcal{L} $. Let $ \mathbf{E} $ be the vector of unknowns $ E[v] $ for non-leaf nodes, and $ \mathbf{b} $ the vector of right-hand sides $ \sum_{u \in N(v)} c_{vu} $. Then the system is $ A \mathbf{E} = \mathbf{b} $, where $ A $ is a symmetric diagonally dominant matrix derived from the tree structure. We are to compute $ E[0] $, the expected cost starting from node $ 0 $, and output $ a \cdot b^{-1} \mod (10^9 + 7) $, where $ E[0] = \frac{a}{b} $ in lowest terms. --- **Formal Output Requirement:** Compute $ E[0] = \frac{a}{b} \in \mathbb{Q} $, reduced, and output $ a \cdot b^{-1} \mod (10^9 + 7) $. The system is defined on a tree with $ n \leq 10^5 $, and edge weights $ c_{uv} \in [1, 10^4] $.