CF833D Red-Black Cobweb

 Slastyona 喜欢观察附近树林里居民的生活。这次，她看到一只奇怪的红黑蜘蛛停留在一个巨大蜘蛛网的中心。 蜘蛛网是由 $n$ 个节点通过丝线连接而成的，每条丝线要么是红色，要么是黑色。通过这些丝线，蜘蛛可以在节点之间移动。没有丝线连接一个节点到它自身，并且任意两个节点之间存在唯一的丝线序列连接它们。 Slastyona 决定研究蜘蛛网的一些特殊性质。她注意到每条丝线都有一个黏稠度值 $x$。 然而，Slastyona 主要对蜘蛛网的 **胶状度** 感兴趣。考虑所有满足以下条件的节点对之间的最短路径：路径上红色丝线和黑色丝线的数量相差至多两倍（即最大数量不超过最小数量的两倍）。对于每条这样的路径，计算路径上所有丝线黏稠度的乘积。蜘蛛网的胶状度是所有这样的路径得到的乘积的总乘积。仅方向不同但节点相同的路径只计算一次。 当然，这个数字可能非常大，所以 Slastyona 请求你计算给定蜘蛛网的胶状度，并将答案对 $10^{9}+7$ 取模后输出。

第一行包含节点数 $n$ ($2 \le n \le 10^{5}$)。 接下来的 $n-1$ 行每行包含四个整数，描述蜘蛛网的第 $i$ 条丝线：它连接的两个节点 $u_i, v_i$ ($1 \le u_i \le n, 1 \le v_i \le n$)，丝线的黏稠度 $x_i$ ($1 \le x \le 10^{9}+6$)，以及丝线的颜色 $c_i$ ($c_i \in \{0, 1\}$)。红色用 $0$ 表示，黑色用 $1$ 表示。

输出单个整数，表示蜘蛛网的胶状度对 $10^{9}+7$ 取模的结果。如果不存在满足“红色和黑色丝线数量相差至多两倍”条件的路径，则输出 $1$。

在第一个样例中，有 $4$ 对节点满足“路径上两种颜色的丝线数量相差至多两倍”的条件。这些节点对是：$(1,3)$，黏稠度乘积为 $45$；$(1,5)$，乘积为 $45$；$(3,4)$，乘积为 $25$；$(4,5)$，乘积为 $25$。蜘蛛网的胶状度等于 $1265625$。 翻译由 DeepSeek V3 完成