## Revamped Version

Di TROC, terdapat sebuah senjata ajaib. Karena satu dan lain hal, Anda ditugaskan oleh kepala TROC untuk menyimpan senjata itu. Senjata tersebut dideskripsikan dengan sebuah barisan bilangan $A$ sepanjang $N$: $[A_1, A_2, ..., A_N]$.

**Kegagahan** suatu barisan $X$ merupakan perkalian dari semua bilangan penyusun $X$. Secara khusus, kegagahan dari suatu barisan kosong adalah $1$.

Adapun **kekuatan** dari senjata tersebut pada waktu $t$, ditulis $S_t$, didefinisikan sebagai jumlah dari kegagahan semua barisan $A'$ yang merupakan subsekuens dari $A$.

Secara formal, $S_t$ dapat didefinisikan sebagai

$$
S_t = \sum_{A' \text{ subsekuens } A} \left( \prod_{i = 1}^{|A'|} i \right).
$$

Anda memiliki empat orang teman: Zit, Maw, Jel, dan Cis. Karena Anda nakal, Anda ingin bermain-main dengan senjata itu selama $D$ hari. Pada pagi hari $h$, Anda akan memberikan senjata itu kepada salah seorang teman Anda, dan malam harinya Anda akan mengambilnya kembali. Teman mana yang Anda berikan senjata bergantung pada karakter $C_h$.

- Jika $C_h = \texttt{Z}$, Anda akan memberikan senjata kepada Zit. Zit akan **mengalikan tepat satu elemen** pada barisan $A$ dengan $E_h$ sedemikian sehingga **kekuatan senjata tersebut minimum**.
- Jika $C_h = \texttt{M}$, Anda akan memberikan senjata kepada Maw. Maw akan **mengalikan tepat satu elemen** pada barisan $A$ dengan $E_h$ sedemikian sehingga **kekuatan senjata tersebut maksimum**.
- Jika $C_h = \texttt{J}$, Anda akan memberikan senjata kepada Jel. Jel akan **mengganti nilai suatu elemen pada barisan $A$ dari $F_h$ menjadi $E_h$**.
- Jika $C_h = \texttt{C}$, Anda akan memberikan senjata kepada Cis. Cis akan **menambahkan sebuah elemen $E_h$ di akhir barisan $A$**.

Untuk setiap hari $h$, Anda harus mengeluarkan nilai $S_h$. Karena $S_h$ bisa jadi sangat besar, keluarkan nilainya modulo $1 \, 000 \, 000 \, 007$.

### Batasan

- $1 \leq N, D \leq 100 \, 000$
- Untuk setiap waktu $t$ di mana $1 \leq t \leq D$:
- $1 \leq |A| \leq 100 \, 000$
- $1 \leq A_i \leq 10^9$ untuk $1 \leq i \leq |A|$
- $C_t \in \{ \texttt{Z}, \texttt{M}, \texttt{J}, \texttt{C} \}$
- $1 \leq E_t \leq 10^9$
- $1 \leq F_t \leq |A|$ apabila $C_t = \texttt{J}$
- Dijamin bahwa apabila $C_t = \texttt{J}$, telah terdapat setidaknya satu elemen bernilai $F_t$ pada barisan $A$

## Original Version

Di TROC, terdapat sebuah senjata ajaib. Karena satu dan lain hal, Anda ditugaskan oleh kepala TROC untuk menyimpan senjata itu. Senjata tersebut dideskripsikan dengan sebuah barisan bilangan $A$ sepanjang $N$: $[A_1, A_2, ..., A_N]$. **Kekuatan** dari senjata tersebut pada waktu $t$, ditulis $S_t$, didefinisikan sebagai $A_1 + A_1A_2 + \cdots + A_1A_2...A_N$. Secara formal, jika pada waktu $t$, panjang barisan $A$ adalah $m$, maka

$$
S_t = \sum_{i = 1}^{m} \left( \prod_{j = 1}^{i} A_j \right).
$$

Anda memiliki empat orang teman: Zit, Maw, Jel, dan Cis. Karena Anda nakal, Anda ingin bermain-main dengan senjata itu selama $D$ hari. Pada pagi hari $h$, Anda akan memberikan senjata itu kepada salah seorang teman Anda, dan malam harinya Anda akan mengambilnya kembali. Teman mana yang Anda berikan senjata bergantung pada karakter $C_h$.

- Jika $C_h = \texttt{Z}$, Anda akan memberikan senjata kepada Zit. Zit akan **mengalikan tepat satu elemen** pada barisan $A$ dengan $E_h$ sedemikian sehingga **kekuatan senjata tersebut minimum**.
- Jika $C_h = \texttt{M}$, Anda akan memberikan senjata kepada Maw. Maw akan **mengalikan tepat satu elemen** pada barisan $A$ dengan $E_h$ sedemikian sehingga **kekuatan senjata tersebut maksimum**.
- Jika $C_h = \texttt{J}$, Anda akan memberikan senjata kepada Jel. Jel akan **mengganti nilai elemen ke-$F_h$ pada barisan $A$ dengan $E_h$**.
- Jika $C_h = \texttt{C}$, Anda akan memberikan senjata kepada Cis. Cis akan **menambahkan sebuah elemen $E_h$ di akhir barisan $A$**. Perhatikan bahwa hal ini dapat mengubah kekuatan senjata tersebut.

Untuk setiap hari $h$, Anda harus mengeluarkan nilai $S_h$. Karena $S_h$ bisa jadi sangat besar, keluarkan nilainya modulo $1 \, 000 \, 000 \, 007$.

### Batasan

- $1 \leq N, D \leq 100 \, 000$
- Untuk setiap waktu $t$ di mana $1 \leq t \leq D$:
- $1 \leq |A| \leq 100 \, 000$
- $1 \leq A_i \leq 10^9$ untuk $1 \leq i \leq |A|$
- $C_t \in \{ \texttt{Z}, \texttt{M}, \texttt{J}, \texttt{C} \}$
- $1 \leq E_t \leq 10^9$
- $1 \leq F_t \leq |A|$ apabila $C_t = \texttt{J}$