题目描述

给定一棵 $n\ (n \le 10^5)$ 个节点的树，边有黑白两色和权值（权值小于 $10^9 + 7$）。求满足黑白边的比例在 $[\frac12,2]$ 的路径边权乘积的乘积。

输入格式

第一行一个整数 $n$，$2 \le n \le 10^5$。

接下来 $n-1$ 行，每行 $4$ 个整数 $u_i, v_i, x_i, c_i$，表示 $u_i$ 与 $v_i$ 之间存在一条权值为 $x_i$，颜色为 $c_i$ 的边。$1 \le u_i, v_i \le n$，$1 \le x_i \le 10^9+6$，$c_i = 0$ 表示白色，$c_i=1$ 表示黑色。

输出格式

一个整数，表示答案对 $10^9+7$ 取余的结果。如果不存在满足条件的路径，输出 $1$。

5
1 2 9 0
2 3 5 1
2 4 5 0
2 5 5 1

1265625

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

452841614