H. Вложенные циклы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бегимай вернулась домой после соревнования — и её встретила очень радостная младшая сестра Динара.

Динара сказала, что она пристально следила за соревнованием — и даже придумала, как решать одну непростую задачу!

Единственное, в чём Динара пока сомневалась — насколько эффективным было придуманное ею решение. Поэтому Динара подготовила псевдокод своего решения, чтобы Бегимай его оценила.

Псевдокод Динары представляет собой комбинацию операторов трёх типов:

  • операция for и следующее за ней целое число $$$k$$$ означает начало цикла из $$$k$$$ итераций;
  • операция end означает конец цикла, заданного ближайшим неоконченным оператором for;
  • операция calc и следующее за ней целое число $$$k$$$ означает вычисления, выполняемые суммарно за $$$k$$$ операций.

Теперь Бегимай должна определить суммарное количество операций, выполняемых данным решением, и сделать вывод из его эффективности.

Бегимай сразу увидела, что итоговое суммарное количество операций получилось просто огромным — и, чтобы слишком не расстраивать сестру, решила сказать ей остаток от деления данного количества на число $$$10^9 + 7$$$.

Входные данные

В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество строк в псевдокоде решения.

Каждая из следующих $$$n$$$ строк содержит один из трёх операторов:

  • разделённые пробелом строка for и целое число $$$k$$$ $$$(1 \le k \le 10^9)$$$ — начало цикла из $$$k$$$ итераций;
  • строка end — конец цикла, заданного ближайшим неоконченным оператором for;
  • разделённые пробелом строка calc и целое число $$$k$$$ $$$(1 \le k \le 10^9)$$$ — вычисления, выполняемые суммарно за $$$k$$$ операций.

Гарантируется, что

  • каждый оператор end соответствует какому-либо оператору for в одной из предыдущих строк;
  • каждый оператор for имеет соответствующий ему оператор end в одной из последующих строк;
  • каждая пара for — end содержит хотя бы один вложенный оператор.
Выходные данные

Пусть $$$T$$$ — суммарное количество операций, выполняемых описанным решением.

В таком случае выведите единственное целое число — остаток от деления $$$T$$$ на $$$10^9 + 7$$$.

Примеры
Входные данные
13
for 10
for 300
calc 5
end
for 40
calc 7
calc 4
end
end
calc 45
for 3
calc 123
end
Выходные данные
19814
Входные данные
7
for 2000
for 1000
for 3000
calc 4000
end
end
end
Выходные данные
999832007
Примечание

Первый тестовый пример

Декомпозируем представленный псевдокод:

  • в строках $$$2$$$ — $$$4$$$ выполняется $$$300 \cdot 5 = 1500$$$ операций;
  • в строках $$$5$$$ — $$$8$$$ выполняется $$$40 \cdot (7 + 4) = 440$$$ операций;
  • в строках $$$1$$$ — $$$9$$$ выполняется $$$10 \cdot (1500 + 440) = 19400$$$ операций;
  • в строке $$$10$$$ выполняется $$$45$$$ операций;
  • в строках $$$11$$$ — $$$13$$$ выполняется $$$3 \cdot 123 = 369$$$ операций.

Суммарно получается $$$T = 19400 + 45 + 369 = 19814$$$ операций.

Второй тестовый пример

Суммарно данное решение выполняет $$$T = 2000 \cdot 1000 \cdot 3000 \cdot 4000 = 24 \cdot 10^{12}$$$ операций.

Необходимо вывести остаток от деления $$$T$$$ на $$$10^9 + 7$$$, который равен $$$999832007$$$.