背景

人們將巴別塔一層層蓋起

期望著能搭到天堂

於是神降下了神罰

人們放棄了抵達天堂

轉而用計算來創造天堂

題面

初始時，有一個變數 $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 的個數一致

子任務

提示

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