AT_iroha2019_day2_j ライ麦畑で待ちながら

[problemUrl]: https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_j 青木さんは高橋君と遊ぶ約束をしていましたが、待てど暮らせど高橋君が来ないので、次のような遊びをすることにしました。 - $ N $ 枚の赤いカードと $ N-1 $ 枚の青いカードを、一列に交互に並べておく。つまり、まず赤いカードを一列に並べ、隣り合う赤いカードの間に青いカードを置く。 - 左から $ i $ 番目の赤いカードには、はじめ非負整数 $ A_i $ が書いてある。 - 左から $ i $ 番目の青いカードには、片方の面に `+` が、他方の面に `×` が書いてある。$ S_i $ が `+` のとき `+` の面が、$ S_i $ が `*` のとき `×` の面がはじめ表向きである。 - 青木さんは、$ Q $ 個のクエリを番号順に実行する。$ i $ 番目のクエリの内容は $ 3 $ つの非負整数 $ T_i,\ X_i,\ Y_i $ で表され、以下のように解釈する。 - $ T_i\ =\ 1 $ のとき、左から $ X_i $ 番目の赤いカードに書かれた整数を $ Y_i $ に書き換える。 - $ T_i\ =\ 2 $ のとき、左から $ X_i $ 番目の青いカードを裏返す。このクエリにおいては、$ Y_i\ =\ 0 $ が保証される。 - $ T_i\ =\ 3 $ のとき(回答クエリ)、左から $ X_i $ 番目の赤いカードを左端、$ Y_i $ 番目の赤いカードを右端とする部分カード列を数式として見て、その計算結果を答える。ただし、青木さんは紙やペンもなしに大きな数を計算できないので、$ 10^9+7 $ で割った余りを答える。 いろはちゃんは、青木さんの答えが合っているか確認するために、上の遊びをシミュレートするプログラムを書くことにしました。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ S $ $ Q $ $ T_1 $ $ X_1 $ $ Y_1 $ $ \vdots $ $ T_Q $ $ X_Q $ $ Y_Q $

各回答クエリの正しい答えをそれぞれ $ 1 $ 行で順に出力してください。

### 制約 - $ S $ は `+`と`*` のみから成る長さ $ N-1 $ の文字列、その他はすべて整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - 各質問 $ T_i,\ X_i,\ Y_i $ について、以下の $ 3 $ つのいずれかが成り立つ - $ T_i\ =\ 1,\ 1\ \leq\ X_i\ \leq\ N,\ 0\ \leq\ Y_i\ \leq\ 10^9 $ - $ T_i\ =\ 2,\ 1\ \leq\ X_i\ \leq\ N\ -\ 1,\ Y_i\ =\ 0 $ - $ T_i\ =\ 3,\ 1\ \leq\ X_i\ \leq\ Y_i\ \leq\ N $ ### 解説 [解説](https://img.atcoder.jp/iroha2019-day2/editorial-J.pdf) ### Sample Explanation 1 $ 1 $行目には、$ 1\times2\times3+4=10 $を出力します。`+`や`×`は、通常の四則演算と同じように計算します。