Problem Statement

You are given a tree with $n$ vertices.
The vertices are numbered $i (0 \leq i < n)$. The root is $0$.
The edges are numbered $i (0 \leq i < n-1)$, and edge $i$ connects vertex $a_i$ and vertex $b_i$.

Each edge $i$ holds a $2 \times 2$ matrix $X_i (0 \leq i < n-1)$. The initial value of $X_i$ is the identity matrix.

Process $q$ queries of the following types.
(1) Update query x
x $i\ x_{00}\ x_{01}\ x_{10}\ x_{11}$
Change $X_i (0 \leq i < n-1)$ to $\begin{pmatrix} x_{00} & x_{01} \\ x_{10} & x_{11}\end{pmatrix}$.
(2) Retrieval query g
g $i\ j$
It is guaranteed that vertex $i$ is an ancestor of vertex $j$.
Output each element, modulo $10^9+7$, of the matrix obtained by multiplying all the matrices on the edges of the path from vertex $i$ to vertex $j$.
Multiply so that the root side is on the left and the leaf side is on the right.

Input

$n$
$a_0\ b_0$
$a_1\ b_1$
$\vdots$
$a_{n-2}\ b_{n-2}$
$q$
$query_1$
$\vdots$
$query_q$

All inputs are integers.

$2 \leq n \leq 100000$
$1 \leq q \leq 20000$

Query x
$0 \leq i < n-1$
$0 \leq x_{st} \leq 1000$

Query g
$0 \leq i, j < n$

It is guaranteed that there is at least $1$ query g.

Output

If the answer is $\begin{pmatrix} c_{00} & c_{01} \\ c_{10} & c_{11}\end{pmatrix}$,
output $c_{00}\ c_{01}\ c_{10}\ c_{11}$ in this order on one line.

Sample

6
0 1
1 3
0 2
2 4
2 5
8
x 2 1 3 0 2
x 3 6 2 8 7
g 0 2
g 0 4
g 0 5
g 2 5
x 4 7 2 4 9
g 0 5

1 3 0 2
30 23 16 14
1 3 0 2
1 0 0 1
19 29 8 18