H. Nested Loops
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Begimai returned home after the competition — and she was greeted by her very happy younger sister Dinara.

Dinara said that she had been closely following the competition — and even came up with a way to solve a challenging problem!

The only thing Dinara was still unsure about was how efficient her proposed solution was. Therefore, Dinara prepared pseudocode of her solution for Begimai to evaluate.

Dinara's pseudocode consists of a combination of three types of operators:

  • The operation for followed by an integer $$$k$$$ indicates the start of a loop with $$$k$$$ iterations;
  • The operation end indicates the end of the loop defined by the nearest unfinished for operator;
  • The operation calc followed by an integer $$$k$$$ indicates calculations performed in total over $$$k$$$ operations.

Now Begimai must determine the total number of operations performed by this solution and draw a conclusion about its efficiency.

Begimai immediately saw that the final total number of operations was simply enormous — and to avoid upsetting her sister too much, she decided to tell her the remainder of this number when divided by $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of lines in the pseudocode of the solution.

Each of the following $$$n$$$ lines contains one of three operators:

  • A space-separated string for and an integer $$$k$$$ $$$(1 \le k \le 10^9)$$$ — the start of a loop with $$$k$$$ iterations;
  • A string end — the end of the loop defined by the nearest unfinished for operator;
  • A space-separated string calc and an integer $$$k$$$ $$$(1 \le k \le 10^9)$$$ — calculations performed in total over $$$k$$$ operations.

It is guaranteed that

  • each end operator corresponds to some for operator in one of the previous lines;
  • each for operator has a corresponding end operator in one of the subsequent lines;
  • each pair of for — end contains at least one nested operator.
Output

Let $$$T$$$ be the total number of operations performed by the described solution.

In this case, output a single integer — the remainder of $$$T$$$ when divided by $$$10^9 + 7$$$.

Examples
Input
13
for 10
for 300
calc 5
end
for 40
calc 7
calc 4
end
end
calc 45
for 3
calc 123
end
Output
19814
Input
7
for 2000
for 1000
for 3000
calc 4000
end
end
end
Output
999832007
Note

First test example

Decomposing the presented pseudocode:

  • In lines $$$2$$$ — $$$4$$$, $$$300 \cdot 5 = 1500$$$ operations are performed;
  • In lines $$$5$$$ — $$$8$$$, $$$40 \cdot (7 + 4) = 440$$$ operations are performed;
  • In lines $$$1$$$ — $$$9$$$, $$$10 \cdot (1500 + 440) = 19400$$$ operations are performed;
  • In line $$$10$$$, $$$45$$$ operations are performed;
  • In lines $$$11$$$ — $$$13$$$, $$$3 \cdot 123 = 369$$$ operations are performed.

In total, $$$T = 19400 + 45 + 369 = 19814$$$ operations.

Second test example

In total, this solution performs $$$T = 2000 \cdot 1000 \cdot 3000 \cdot 4000 = 24 \cdot 10^{12}$$$ operations.

It is necessary to output the remainder of $$$T$$$ when divided by $$$10^9 + 7$$$, which equals $$$999832007$$$.