問題文

12月も折り返し、Y君はクリスマスカードの準備をしているようです。

0 1 2 3 4 5 6 7 8 9 + * のいずれか一つが書かれたカード $N$ 枚の列 $C_1,C_2,\dots ,C_N$ が与えられます。すべてのカードは、+ または * の書かれた演算子カードと、それ以外の数字カードの2種類に分類されます。$C_1,C_N$ は数字カードで、数字カードと演算子カードは1枚ずつ交互に並んでいます。

数字カードを1桁の整数、演算子カード + を加算、* を乗算と見なしたとき、カード列 $C_X,C_{X+1},\dots ,C_Y$ がつくる式の値を $f(X,Y)$ とします。例えば、$C_1=$ 5、$C_2=$ +、$C_3=$ 7、$C_4=$ *、$C_5=$ 4、$C_6=$ +、$C_7=$ 1 のとき、$f(1,5)=5+7\times 4=5+28=33$、$f(5,7)=4+1=5$ となります。

以下の2種類のクエリが $Q$ 個与えられるので、これを順番に処理してください。

• 交換クエリ：同じ種類のカード $C_X$ と $C_Y$ を交換する。
• 質問クエリ：$f(X,Y)mod({10}^9+7)$ を出力する。

入力

$N$
$C_1$ $C_2$ $\dots$ $C_N$
$Q$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$⋮$
$T_Q$ $X_Q$ $Y_Q$

数値はすべて整数です。以下の制約を満たします。

• $3\le N\le {10}^5-1$
• $N$ は奇数
• $i$ が奇数ならば $C_i\in \{$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 $\}$
• $i$ が偶数ならば $C_i\in \{$ +, * $\}$
• $1\le Q\le {10}^5$
• $i\ne Q$ ならば $T_i\in \{$ !, ? $\}$
• $T_Q=$ ?
• $1\le X_i<Y_i\le N$
• $T_i=$ ! のとき、これは交換クエリを表し、
• カード $C_{X_i}$ と $C_{Y_i}$ の種類は同じ (すなわち $X_i\equiv Y_i(\mathrm{mod}2)$)
• $T_i=$ ? のとき、これは質問クエリを表し、
• $X_i,Y_i$ は奇数

出力

すべての質問クエリに対して1行ずつ出力し、最後に改行してください。

サンプル

7
5 + 7 * 4 + 1
6
? 1 5
? 5 7
! 2 4
? 1 5
! 3 7
? 1 7

33
5
39
16