Background

A boy wears a dark gray spring school uniform jacket and black shorts, with a clean white shirt inside.

For some reason, his right hand is wrapped in bandages, and his right eye is tightly covered by his hair, giving off a mysterious feeling.

A bright red higanbana petal spins above the classroom, where no one pays attention.

Qi’s background is always a mystery.

"So who are you, and why did you come here!"

But the higanbana clearly does not want you to know any of that.

Problem Description

Qi gave Han a tree numbered $1\sim n$. Each node originally had a node value, and some edges have edge weights while others do not. However, Qi erased the node values. Han only knows that all node values are integers, and are between $l$ and $r$ (inclusive). Also, node values and edge weights satisfy the following special relationship:

• For edges with edge weights, the sum of the node values of the two endpoints must equal the edge weight.

• For edges without edge weights, there is no restriction.

Qi asks Han how many different ways there are to fill in the node values. Two fillings are different if and only if there exists at least one node whose value is different. However, Han cannot solve this problem.

Han asks you to solve it.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains three integers $n,l,r$, meaning the tree has $n$ nodes, and the node value range is $[l,r]$.

The next $n-1$ lines each start with an integer $op$. If $op=0$, this edge has no edge weight; if $op=1$, this edge has an edge weight.

• If $op=0$, then input two integers $u,v$, meaning this edge connects nodes $u,v$.

• If $op=1$, then input three integers $u,v,w$, meaning there is an edge of weight $w$ connecting nodes $u,v$.

Output Format

For each test case, output one integer per line, representing the number of ways to fill in the node values. The answer should be taken modulo $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

Hint

Sample Explanation

For the first test case in the sample, we can get the following graph:

The $5$ filling methods are:

$\{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\}$

It can be proven that no other filling methods exist.

In the sample input, blank lines were added for readability. In the actual testdata, there are no extra blank lines.

Constraints

This problem uses bundled tests.

Special Property: It is guaranteed that every edge has no edge weight.

For $100\%$ of the data, it is guaranteed that $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\}$.

Translated by ChatGPT 5