CF833D.Red-Black Cobweb

Slastyona likes to watch life of nearby grove's dwellers. This time she watches a strange red-black spider sitting at the center of a huge cobweb.

The cobweb is a set of n nodes connected by threads, each of the treads is either red of black. Using these threads, the spider can move between nodes. No thread connects a node to itself, and between any two nodes there is a unique sequence of threads connecting them.

Slastyona decided to study some special qualities of the cobweb. She noticed that each of the threads has a value of clamminess x.

However, Slastyona is mostly interested in jelliness of the cobweb. Consider those of the shortest paths between each pair of nodes on which the numbers of red and black threads differ at most twice. For each such path compute the product of the clamminess of threads on the path.The jelliness of the cobweb is the product of all obtained values among all paths. Those paths that differ by direction only are counted only once.

Of course, this number can be huge, so Slastyona asks you to compute the jelliness of the given cobweb and print the answer modulo 109 + 7.

斯拉丝蒂奥娜喜欢观察附近树林中居民的生活。这一次，她观察到一只奇特的红黑相间蜘蛛正坐在一张巨大蛛网的中心。

这张蛛网由 $n$ 个节点组成，节点之间通过丝线连接；每条丝线要么是红色，要么是黑色。蜘蛛可借助这些丝线在节点间移动。任意节点不会与自身相连，且任意两个节点之间都存在唯一的一条丝线序列（即路径）将它们连通。

斯拉丝蒂奥娜决定研究这张蛛网的一些特殊性质。她注意到每条丝线上都有一个“黏性值” $x$。

然而，斯拉丝蒂奥娜最感兴趣的是蛛网的“胶质度”（jelliness）。考虑所有节点对之间的最短路径，并仅保留其中满足“红色丝线数量与黑色丝线数量之差的绝对值不超过 2”的那些路径。对每一条这样的路径，计算其上所有丝线的黏性值的乘积。蛛网的胶质度定义为：对所有满足条件的路径所计算出的乘积值，再求其总乘积。若两条路径仅方向相反（即起点终点互换），则视为同一条路径，仅计一次。

当然，该数值可能极其巨大，因此斯拉丝蒂奥娜请你计算给定蛛网的胶质度，并将结果对 $10^9 + 7$ 取模后输出。

The first line contains the number of nodes n (2 ≤ n ≤ 105).

The next n - 1 lines contain four integers each, denoting the i-th thread of the cobweb: the nodes it connects u__i, v__i (1 ≤ u__i ≤ n, 1 ≤ v__i ≤ n), the clamminess of the thread x__i (1 ≤ x ≤ 109 + 6), and the color of the thread c__i (). The red color is denoted by 0, and the black color is denoted by 1.

第一行包含节点数 $n$（$2 \leq n \leq 10^5$）。

接下来的 $n - 1$ 行每行包含四个整数，表示蛛网的第 $i$ 根丝线：它所连接的两个节点 $u_i,\,v_i$（$1 \leq u_i \leq n$，$1 \leq v_i \leq n$）、该丝线的黏性值 $x_i$（$1 \leq x_i \leq 10^9 + 6$）以及该丝线的颜色 $c_i$（）。红色用 $0$ 表示，黑色用 $1$ 表示。

Print single integer the jelliness of the cobweb modulo 109 + 7. If there are no paths such that the numbers of red and black threads differ at most twice, print 1.

输出一个整数，表示蛛网的“胶状度”对 $10^9 + 7$ 取模的结果。若不存在满足“红色丝线与黑色丝线数量之差的绝对值不超过 2”的路径，则输出 1。

In the first example there are 4 pairs of nodes such that the numbers of threads of both colors on them differ at most twice. There pairs are (1, 3) with product of clamminess equal to 45, (1, 5) with product of clamminess equal to 45, (3, 4) with product of clamminess equal to 25 and (4, 5) with product of clamminess equal to 25. The jelliness of the cobweb is equal to 1265625.

在第一个例子中，有 4 对节点，使得这两节点上两种颜色的丝线数量之比至多为 2。这些节点对分别是：(1, 3)，其黏腻度乘积为 45；(1, 5)，其黏腻度乘积为 45；(3, 4)，其黏腻度乘积为 25；以及 (4, 5)，其黏腻度乘积为 25。该蛛网的胶状度为 1265625。