在 ICPCCamp 中，有 $n$ 个城市和 $(n-1)$ 条（双向）道路连接这些城市。第 $i$ 条道路连接第 $a_i$ 个城市和第 $b_i$ 个城市。保证城市之间是连通的。

最近，在第 $a_i$ 个城市和第 $b_i$ 个城市之间又新建了 $2 \times c_i - 1$ 条道路。Bobo 很快想出了一个环游世界的计划！他计划从城市 1 出发，在恰好经过每一条道路各一次后回到城市 1。

显然，Bobo 有许多计划可以选择。他想求出不同计划的数量，结果对 $(10^9 + 7)$ 取模。

注意，两个计划 $A$ 和 $B$ 被视为不同，当且仅当存在一个 $i$，使得计划 $A$ 中第 $i$ 次经过的道路与计划 $B$ 中第 $i$ 次经过的道路不同。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)。

接下来的 $(n-1)$ 行中，第 $i$ 行包含 3 个整数 $a_i, b_i, c_i$ ($1 \le a_i, b_i \le n, c_i \ge 1, c_1 + c_2 + \dots + c_{n-1} \le 10^6$)。

输出格式

输出一个整数，表示计划的数量对 $(10^9 + 7)$ 取模的结果。

样例

样例输入 1

3
1 2 1
2 3 1

样例输出 1

4

样例输入 2

3
1 2 1
1 3 2

样例输出 2

144