Problem B
Not too close please!

Illustration of Sample Input 2

Kia’s morning commute is a battlefield. The bus is packed, people are breathing down each other’s necks, and personal space is a myth. But Kia notices something fascinating: despite the chaos, people naturally avoid standing directly next to each other when possible. It’s like an unspoken rule of public transit survival. Come to think of it, the same thing happens in crowded elevators, cramped subway cars, even at packed concerts; anywhere people are squeezed together, they instinctively try to maximize their bubble of space.

Stuck in the crowd with nothing but time, Kia starts analyzing the pattern. He visualizes the bus layout as a tree structure. Each seat and standing spot is a node, connections between spots are edges. A question emerges: How many valid arrangements exist where nobody has to suffer the awkwardness of being shoulder-to-shoulder?

Kia considers $2$ specific scenarios. He picks two spots $x$ and $y$ on the bus and wonders: if exactly $r$ people need to stand along the route between them, how many ways can they arrange themselves without anyone being adjacent? A route between two spots is the unique path from $x$ to $y$.

For the other one, he picks $m$ specific spots to define a region and asks: how many valid arrangements exist for placing people anywhere in that region (with no restriction on how many, just no adjacent pairs)? A region of $m$ spots is the minimal connected subtree containing all $m$ spots.

His friends notice him staring intensely at the bus ceiling, muttering under his breath. One suggests he just listen to music. But Kia can’t let it go; he needs to know the answer.

Input

The first line contains two integers $N$ and $Q$: the number of nodes in the tree and the number of queries $(1 \leq N, Q \leq 5 \cdot 10^5)$. The next $N-1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq N$), representing an edge between nodes $u$ and $v$.

The next $Q$ lines contain the queries. Each query starts with an integer $t \in \{ 1, 2\} $ denoting the query type. If $t = 1$: three integers $x$, $y$, $r$ ($1 \leq x, y \leq N, 0 \leq r \leq 10^9$) follow. If $t = 2$: an integer $m$ follows, then $m$ integers $a_i$ representing the node indices $(2 \leq m \leq N, 1 \leq a_i \leq N)$.

It is guaranteed that $\sum _{i=1}^Q m_i \leq 10^6$ (the total number of nodes across all Type 2 queries is at most $10^6$).

Output

Print $Q$ integers, one per line, representing the answer to each query modulo $10^9 + 7$.

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

3
9
1
5

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

4
0
37
1
8