该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

一个皮肤黢黑的高大男子站在悬崖峭壁旁。
随着他的眼光望去，只见一颗伟岸高大的参天古树。
男子缓缓的低下头，开始了沉思。

题目描述

图灵王的古树是一棵编号为 $1 \sim n$ 的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。但是随着悠久的岁月，古树上面的点权都消失了。图灵王只知道点权都是整数，而且在 $l$ 和 $r$ 之间（包含端点）。而且，点权和边权有着下面的特殊关系：

• 对于任一条输入进来的边，若op = 1，则为有边权的边，要求连接的两个点的点权和为边权。
• 对于任一条输入进来的边，若op = 0，则为没有边权的边，没有任何要求。

图灵王现在在思考这棵树有多少种不同的点权填写方式。两种填写方式不同，当且仅当至少存在一个点的点权不同。

图灵王请求勇者来帮他解决这个问题。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，代表测试数据组数。

对于每一组测试数据：

第一行三个整数 $n,l,r$，代表树上点的个数是 $n$，点权的范围是 $[l,r]$。

接下来 $n-1$ 行，每行先输入一个整数 $op$，$op=0$ 表示这条边没有边权，$op=1$ 表示这条边有边权。

• 如果 $op=0$，再输入两个整数 $u,v$，表示这条边连接 $u,v$ 两个点。
• 如果 $op=1$，再输入三个整数 $u,v,w$，表示有一条权值为 $w$ 的边连接 $u,v$ 两个点。

输出格式

对于每个测试点，输出一行一个整数，代表点权填写方式的个数。答案对 $10^9+7$ 取模。

2
6 0 4
1 1 2 2
1 2 3 4
1 3 4 2
0 2 5
1 4 6 3

6 -1 4
1 1 2 4
0 2 3
0 3 4
0 2 5
0 4 6

5
6480

提示

样例解释

对于样例的第一组测试数据，可以得到下图：

$5$ 种填写方式分别为：

$\{0,2,2,0,0,3\}\\\{0,2,2,0,1,3\}\\\{0,2,2,0,2,3\}\\\{0,2,2,0,3,3\}\\\{0,2,2,0,4,3\}$

可以证明，不存在别的填写方式。

样例输入中，为了直观，添加了空行。实际数据中不存在多余空行。

数据范围

本题采用捆绑测试。

特殊性质：保证每条边都无边权。

对于 $100\%$ 的数据，保证 $1\le T \le 5$，$1\le n\le 2\times10^5$，$1\le \sum n\le 10^6$，$-10^9\le l\le r \le 10^9$，$-10^9\le w\le 10^9$，$op\in\{0,1\}$。