問題文

漸化式で定義される数列$a_i, b_i (0 \leq i \leq 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 \leq i < n)$は$2 n$個の漸化式のパラメータである。これらの初期値は$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$
$query_1$
$\vdots$
$query_q$

入力は全て整数。

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

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

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

クエリa
a $i$
$0 \leq i \leq 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