問題文

頂点$n$からなる木が与えられる。
頂点には番号$i(0\le i<n)$がついている。根は$0$である。
辺には番号$i(0\le i<n-1)$がついており、辺$i$は頂点$a_i$と頂点$b_i$を繋ぐ。

各辺$i$には、$2\times 2$行列$X_i(0\le i<n-1)$が載っている。$X_i$の初期値は単位行列である。

以下のクエリを$q$個処理せよ。
(1) 変更クエリx
x $i{x}_{00}{x}_{01}{x}_{10}{x}_{11}$
$X_i(0\le i<n-1)$を$\left(\begin{array}{cc}{x}_{00}& x_{01}\\ x_{10}& x_{11}\end{array}\right)$に変更する。
(2) 取得クエリg
g $ij$
頂点$i$は頂点$j$の先祖であることが保証される。
頂点$i$から頂点$j$へのパスの辺に載っている行列を、すべて掛けた行列の各要素を${10}^9+7$で割った出力する。
根側が左、葉側が右になるほうにかける。

入力

$n$
$a_0{b}_0$
$a_1{b}_1$
$⋮$
$a_{n-2}{b}_{n-2}$
$q$
$quer{y}_1$
$⋮$
$quer{y}_q$

入力は全て整数。

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

クエリx
$0\le i<n-1$
$0\le x_{st}\le 1000$

クエリg
$0\le i,j<n$

クエリgが$1$個以上あることが保証される。

出力

答えが$\left(\begin{array}{cc}{c}_{00}& c_{01}\\ c_{10}& c_{11}\end{array}\right)$であれば、
$c_{00}{c}_{01}{c}_{10}{c}_{11}$の順番で一行で出力せよ。

サンプル

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