Slastyona 喜欢观察附近树林居民的生活。这次她看到一只奇怪的红黑蜘蛛坐在一张巨大的蜘蛛网的中心。
蜘蛛网是由线程连接的 n 个节点的集合,每个踏板都是红色或黑色。使用这些线程,蜘蛛可以在节点之间移动。没有线程将节点连接到自身,并且在任何两个节点之间都有唯一的线程序列连接它们。
Slastyona 决定研究蜘蛛网的一些特殊品质。她注意到每条线的粘性值为 x。
然而,Slastyona 最感兴趣的是蜘蛛网的果冻状。考虑每对节点之间的最短路径,其中红线和黑线的数量最多相差两次。对于每个这样的路径,计算路径上线程的粘性的乘积。蜘蛛网的粘性是所有路径中所有获得的值的乘积。那些仅方向不同的路径仅计算一次。
当然,这个数字可能很大,因此 Slastyona 要求您计算给定蜘蛛网的果冻度并打印模 109 + 7 的答案。
输入
第一行包含节点数 n (2 ≤ n ≤ 105)。
接下来的 n - 1 行每行包含四个整数,表示蜘蛛网的第 i 个线程:它连接的节点 ui, vi (1 ≤ ui ≤ n, 1 ≤ vi ≤ n),线程 xi 的粘稠度 (1 ≤ x ≤ 109 + 6),以及线程 ci 的颜色 ($$c_i \in \{0, 1\}$$)。红色用0表示,黑色用1表示。
输出
打印蜘蛛网的胶状度以 109 + 7 为模的单个整数。如果不存在使得红线和黑线的数量最多相差两次的路径,则打印 1。
示例
输入 #1
5 1 2 9 0 2 3 5 1 2 4 5 0 2 5 5 1
输出 #1
1265625
输入 #2
8 1 2 7 1 2 3 4 1 3 4 19 1 5 1 2 0 6 2 3 0 7 3 3 0 8 4 4 0
输出 #2
452841614
注意
在第一个示例中,有 4 对节点,其上两种颜色的线程数最多相差两倍。存在对 (1, 3),其粘性乘积等于 45,(1, 5),其粘性乘积等于 45,(3, 4),其粘性乘积等于 25,以及 (4, 5),其粘性乘积等于 25。蜘蛛网的胶冻度等于 1265625。