問題文

漸化式で定義される数列$a_i,b_i(0\le i\le n)$がある。

$a_{i+1}=x_i{b}_i^2+a_i$
$b_{i+1}=y_i{b}_i+1$
$a_0=b_0=1$

$x_i,y_i(0\le i<n)$は$2n$個の漸化式のパラメータである。これらの初期値は$0$である。
以下のクエリを$q$個処理せよ。

(1) $x$ $i$ $v$
$x_i$を$v$に変更する。
(2) $y$ $i$ $v$
$y_i$を$v$に変更する。
(3) $a$ $i$
$a_i$を${10}^9+7$で割った余りを出力する。

入力

$n$
$q$
$quer{y}_1$
$⋮$
$quer{y}_q$

入力は全て整数。

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

クエリx
x $i$ $v$
$0\le i<n$
$0\le v\le 100000$

クエリy
y $i$ $v$
$0\le i<n$
$0\le v\le 100000$

クエリa
a $i$
$0\le i\le n$

クエリaは少なくとも1つあることが保証される。

出力

各クエリaのあとに改行してください。

サンプル

2
7
a 2
x 1 1
y 0 3
y 1 2
a 2
y 0 0
a 2

1
17
2

4
17
x 3 67829
x 2 98198
y 2 18912
y 3 67274
x 3 7010
a 1
x 0 9635
a 0
a 3
x 3 5394
a 1
a 4
y 1 3076
a 3
x 1 8612
y 1 55697
a 4

1
1
107834
9636
442357517
731695075
252637976