You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

背景

人們將巴別塔一層層蓋起

期望著能搭到天堂

於是神降下了神罰

人們放棄了抵達天堂

轉而用計算來創造天堂

題面

初始時，有一個變數 $X$ 的值為 $0$。

給定一個長度為 $N$ 的操作序列。請你依序執行序列中的所有操作，並計算出操作完全結束後，變數 $X$ 的最終數值。為了避免數字過大，所有的計算過程與結果都必須在模 $P$（$P = 10^9 + 7$）的意義下進行。

操作序列由四種指令構成，部分指令會附帶一個整數參數 $b$：

• a C：把 $X$ 更新為 $(X + C) \pmod P$。
• m C：把 $X$ 更新為 $(X \times C) \pmod P$。
• f B：代表一個迴圈的開始。將此 f 指令與其配對的 e 指令之間的所有操作，重複執行 $B$ 次。（f 與 e 的配對規則等同於括號配對）。
• e：代表當前所在迴圈的結束。

請輸出操作序列執行完畢後，$X$ 的最終數值。

輸入格式

第一行為一個正整數，為 $N$ 的值 隨後有 $N$ 行輸入，每一行的輸入為題面中四種指令的格式之一

輸出格式

應有一行，為 X 在操作序列后的值

範例

3
a 1
m  10
a  2

12

2
a 1000000000
a 8

1

5
a 1
f 3
m 10
e
a 2

1002

6
f 2
a 1
f 3
m 10
e
e

1001000

數據範圍

• $1 \leq n \leq 10^5$
• $1 \leq C,B \leq 10^9$
• 保證 f 和 e 的個數一致

子任務

提示

和那座塔一樣，這道題也可以一步一步來