<center></center>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.
## Input
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.
## Output
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.
[samples]
## Note
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.
Slastyona 喜欢观察附近树林居民的生活。这一次，她观察到一只奇特的红黑蜘蛛坐在一个巨大蛛网的中心。
这个蛛网由 #cf_span[n] 个节点和若干线段组成，每条线段要么是红色，要么是黑色。蜘蛛可以通过这些线段在节点间移动。没有线段连接节点到自身，且任意两个节点之间有且仅有一条由线段组成的唯一路径。
Slastyona 决定研究蛛网的一些特殊性质。她注意到每条线段都有一个 _黏性_ 值 #cf_span[x]。
然而，Slastyona 更感兴趣的是蛛网的 _果冻度_。考虑所有节点对之间的最短路径中，红色线段与黑色线段的数量之差至多为 2 的那些路径。对于每条这样的路径，计算其上所有线段黏性值的乘积。蛛网的 _果冻度_ 是所有这些路径乘积的乘积。仅当路径方向不同时视为同一条路径，因此只计一次。
当然，这个数字可能非常大，因此 Slastyona 要求你计算给定蛛网的果冻度，并输出结果对 #cf_span[109 + 7] 取模的值。
第一行包含节点数 #cf_span[n] #cf_span[(2 ≤ n ≤ 105)]。
接下来的 #cf_span[n - 1] 行，每行包含四个整数，表示蛛网的第 #cf_span[i] 条线段：它连接的两个节点 #cf_span[ui, vi] #cf_span[(1 ≤ ui ≤ n, 1 ≤ vi ≤ n)]，线段的 _黏性_ 值 #cf_span[xi] #cf_span[(1 ≤ x ≤ 109 + 6)]，以及线段的颜色 #cf_span[ci]（）。红色用 #cf_span[0] 表示，黑色用 #cf_span[1] 表示。
输出一个整数，表示蛛网的 _果冻度_ 对 #cf_span[109 + 7] 取模的结果。如果没有满足红色与黑色线段数量之差至多为 2 的路径，请输出 #cf_span[1]。
在第一个例子中，有 #cf_span[4] 对节点满足路径上红黑线段数量之差至多为 2。这些节点对分别是 #cf_span[(1, 3)]，其黏性乘积为 #cf_span[45]；#cf_span[(1, 5)]，其黏性乘积为 #cf_span[45]；#cf_span[(3, 4)]，其黏性乘积为 #cf_span[25]；以及 #cf_span[(4, 5)]，其黏性乘积为 #cf_span[25]。蛛网的 _果冻度_ 为 1265625。
## Input
第一行包含节点数 #cf_span[n] #cf_span[(2 ≤ n ≤ 105)]。接下来的 #cf_span[n - 1] 行，每行包含四个整数，表示蛛网的第 #cf_span[i] 条线段：它连接的两个节点 #cf_span[ui, vi] #cf_span[(1 ≤ ui ≤ n, 1 ≤ vi ≤ n)]，线段的 _黏性_ 值 #cf_span[xi] #cf_span[(1 ≤ x ≤ 109 + 6)]，以及线段的颜色 #cf_span[ci]（）。红色用 #cf_span[0] 表示，黑色用 #cf_span[1] 表示。
## Output
输出一个整数，表示蛛网的 _果冻度_ 对 #cf_span[109 + 7] 取模的结果。如果没有满足红色与黑色线段数量之差至多为 2 的路径，请输出 #cf_span[1]。
[samples]
## Note
在第一个例子中，有 #cf_span[4] 对节点满足路径上红黑线段数量之差至多为 2。这些节点对分别是 #cf_span[(1, 3)]，其黏性乘积为 #cf_span[45]；#cf_span[(1, 5)]，其黏性乘积为 #cf_span[45]；#cf_span[(3, 4)]，其黏性乘积为 #cf_span[25]；以及 #cf_span[(4, 5)]，其黏性乘积为 #cf_span[25]。蛛网的 _果冻度_ 为 1265625。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 10^5 $, be the number of nodes.
Let $ T = \{ (u_i, v_i, x_i, c_i) \mid i \in \{1, \dots, n-1\} \} $ be the set of edges, where:
- $ u_i, v_i \in \{1, \dots, n\} $ are the endpoints,
- $ x_i \in \mathbb{Z} $, $ 1 \leq x_i \leq 10^9 + 6 $, is the clamminess,
- $ c_i \in \{0, 1\} $ is the color (0 = red, 1 = black).
The graph is a tree: undirected, connected, with no cycles, and exactly one unique path between any pair of nodes.
For any unordered pair of distinct nodes $ \{p, q\} $, let $ \pi_{p,q} $ denote the unique path from $ p $ to $ q $.
Let $ r_{p,q} $ be the number of red edges (color 0) on $ \pi_{p,q} $, and $ b_{p,q} $ the number of black edges (color 1).
Let $ d_{p,q} = |r_{p,q} - b_{p,q}| $.
Let $ P = \{ \{p, q\} \mid 1 \leq p < q \leq n,\ d_{p,q} \leq 2 \} $ be the set of unordered node pairs satisfying the condition.
For each $ \{p, q\} \in P $, define the path product:
$$
\prod_{e \in \pi_{p,q}} x_e
$$
**Constraints**
1. The graph is a tree with $ n $ nodes and $ n-1 $ edges.
2. For each edge $ e \in T $, $ 1 \leq x_e \leq 10^9 + 6 $, $ c_e \in \{0, 1\} $.
3. All computations are modulo $ M = 10^9 + 7 $.
**Objective**
Compute the jelliness:
$$
J = \prod_{\{p,q\} \in P} \left( \prod_{e \in \pi_{p,q}} x_e \right) \mod M
$$
If $ P = \emptyset $, then $ J = 1 $.