D. Madhav's Supercharging Nodes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes and $$$n-1$$$ edges. Every edge $$$(u,v)$$$ has $$$w$$$ markable points. Each markable point can be marked at most once.

Each node $$$i$$$ has a permitted range $$$[l_i, r_i]$$$. Let $$$m_i$$$ denote the total number of marked points on edges incident to node $$$i$$$. For every node, the condition $$$l_i \le m_i \le r_i$$$ must hold.

You may choose any subset of nodes to supercharge. If node $$$i$$$ is supercharged:

  • Its permitted range becomes $$$[2l_i, 2r_i]$$$
  • The number of markable points on every edge incident to $$$i$$$ reduces by one

If both nodes at the endpoints of an edge $$$(u,v)$$$ are supercharged, then the markable points on that edge reduces by 2 (1 because of each supercharged node).

You are allowed to mark at most $$$x$$$ points in total across the entire tree.

Your task is to compute the number of valid ways (respecting the permitted ranges of all nodes) to choose supercharged nodes and marked points, modulo $$$10^9 + 7$$$.

Two ways are considered identical if and only if:

  • The set of supercharged nodes is the same, and
  • The set of marked points is exactly the same.
If an edge has 3 markable points, then marking the 1st and 3rd is considered distinct to marking the 1st and 2nd.
Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 250)$$$ — the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 250$$$, $$$0 \le x \le 25$$$).

The next $$$n-1$$$ lines describe the edges. Each line contains three integers $$$a$$$, $$$b$$$, and $$$w$$$ ($$$1 \le a,b \le n$$$, $$$a \ne b$$$, $$$2 \le w \le 2 \cdot 10^5$$$), describing an edge between nodes $$$a$$$ and $$$b$$$ of length $$$w$$$. It is guaranteed that the edges provided form a valid tree.

The next $$$n$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le x$$$), describing the permitted range of node $$$i$$$.

Additional Constraints:

  • The sum of $$$n$$$ across all test cases doesn't exceed 250
  • The sum of $$$x$$$ across all test cases doesn't have an additional bound
Output

For each test case, output a single integer, the number of valid ways modulo $$$10^9 + 7$$$.

Example
Input
4
2 1
1 2 2
0 1
0 1
2 2
1 2 2
1 2
0 2
3 1
1 2 10
1 3 20
0 1
1 1
0 0
5 10
1 2 10
1 3 9
2 4 15
2 5 7
1 3
1 2
1 2
0 2
0 2
Output
8
4
38
13510619
Note

If an edge has 1 markable point, let its name be a, and if the edge has 2 markable points, let their names be a and b.

For the first test case:

  • Supercharged Set: {} -> Mark Nothing, a, or b [3 ways]
  • Supercharged Set: {1} -> Mark Nothing or a [2 ways]
  • Supercharged Set: {2} -> Mark Nothing or a [2 ways]
  • Supercharged Set: {1,2} -> Mark Nothing [1 way]
  • Hence we get a total of 8 ways.

For the second test case:

  • Supercharged Set: {} -> Mark a, b or both [3 ways]
  • Supercharged Set: {1} -> No Valid Configuration [0 ways]
  • Supercharged Set: {2} -> Mark a [1 way]
  • Supercharged Set: {1,2} -> No Valid Configuration [0 ways]
  • Hence we get a total of 4 ways.

For the third test case:

  • Supercharged Set: {} -> Mark on edge (1,2) [10 ways]
  • Supercharged Set: {1} -> Mark on edge (1,2) [9 ways]
  • Supercharged Set: {2} -> No Valid Configuration [0 ways]
  • Supercharged Set: {3} -> Mark on edge (1,2) [10 ways]
  • Supercharged Set: {1,2} -> No Valid Configuration [0 ways]
  • Supercharged Set: {1,3} -> Mark on edge (1,2) [9 ways]
  • Supercharged Set: {2,3} -> No Valid Configuration [0 ways]
  • Supercharged Set: {1,2,3} -> No Valid Configuration [0 ways]
  • Hence we get a total of 38 ways.

We will refrain from manually listing out the possibilities of the fourth test case.