H. Стек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим стек, который поддерживает выполнение двух типов действий:

  • Добавить заданное число в стек.
  • Извлечь два числа из стека, произвести над ними арифметическую операцию (сложение или умножение) и добавить результат этой арифметической операции в стек.

Вам задана строка, описывающая последовательность действий над стеком. i-ый символ строки соответствует i-ому действию, которое надо выполнить:

  • Если i-й символ является цифрой, то нужно добавить в стек число, соответствующее этой цифре.
  • Если i-й символ «+» или «*», то нужно выполнить арифметическую операцию, соответствующую этому символу.

Изначально стек пуст. Выведите число, которое окажется на вершине стека после выполнения всех заданных действий.

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

В единственной строке входных данных задана непустая строка действий над стеком, состоящая из символов «+», «*» и цифр (0..9). Длина строки от 1 до 20 символов, включительно.

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

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

Выведите единственное число — верхний элемент стека после выполнения заданных операций.

Примеры
Входные данные
12+3*66*+
Выходные данные
45
Входные данные
149
Выходные данные
9
Примечание

В первом примере действия над стеком эквивалентны вычислению выражения (1+2)*3+6*6.

Во втором примере используется только добавление чисел в стек, и ответом будет последнее добавленное число.