Задачі
Дужки
Дужки
Дано вираз, що складається лише з букв \textbf{а} та знаків операцій \textbf{+} і \textbf{*}. Напишіть програму, яка обчисляює кількість способів розстановки повного набору дужок у цьому виразі таким чином, щоб кожна пара дужок містила один знак операції і два операнди, кожен з яких є або буквою \textbf{а}, або виразом в дужках. Значення виразу при цьому повинно залишатись попереднім, тобто спочатку повинні виконуватись операції множення, а потім додавання. Наприклад, для виразу \textbf{а }+ \textbf{а }+ \textbf{а }* \textbf{а }* \textbf{а} існує \textbf{4} способи розстановки дужок:
(а+(а+(а*(а*а))))
(а+(а+((а*а)*а)))
((а+а)+((а*а)*а))
((а+а)+(а*(а*а)))
\InputFile
У першому рядку міститься коректний вираз, що містить не більше \textbf{25 }знаків операцій.
\OutputFile
Вивести кількість способів розстановки дужок.
Вхідні дані #1
a+a+a*a*a
Вихідні дані #1
4