题目背景

少年身着春季校服的深灰色外套与黑色短裤，外套内是白净的衬衫。

他的右手不知为何缠着绷带，右眼用头发挡得严严实实，扑面而来的是一种神秘感。

一瓣鲜红的彼岸花，在教室上空无人在意之处打旋。

玘的身世，总是一个谜题吧。

「所以你到底是什么人，又为什么要来这里！」

可是彼岸花显然不想让你知道这些。

题目描述

玘给了寒一棵编号为 $1\sim n$ 的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。可是玘把每一个点的点权删除了。寒只知道点权都是整数，而且在 $l$ 和 $r$ 之间（包含端点）。而且，点权和边权有着下面的特殊关系：

• 对于有边权的边，要求连接的两个点的点权和为边权。

• 对于没有边权的边，无限制。

玘问寒这棵树有多少种不同的点权填写方式。两种填写方式不同，当且仅当至少存在一个点的点权不同。可是寒不会做这个题。

寒请你解决这个问题。

输入格式

本题有多组测试数据。

第一行一个整数 $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\}$

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

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

数据范围

本题采用捆绑测试。

子任务编号	数据范围	特殊性质	分值
$\text{Subtask1}$	$1\le n\le 10$，$0\le l,r\le5$		$15$
$\text{Subtask2}$	$1\le n\le 2\times 10^5$，$0\le l,r\le5$		$20$
$\text{Subtask3}$	$1\le n\le 10$，$-10^9\le l,r\le 10^9$		$15$
$\text{Subtask4}$	$1\le n\le 2\times10^5$，$-10^9\le l,r\le 10^9$	有	$10$
$\text{Subtask5}$			$40$

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

对于 $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\}$。