Дужки

Дано вираз, що складається лише з букв а та знаків операцій + і *. Напишіть програму, яка обчисляює кількість способів розстановки повного набору дужок у цьому виразі таким чином, щоб кожна пара дужок містила один знак операції і два операнди, кожен з яких є або буквою а, або виразом в дужках. Значення виразу при цьому повинно залишатись попереднім, тобто спочатку повинні виконуватись операції множення, а потім додавання. Наприклад, для виразу а + а + а * а * а існує 4 способи розстановки дужок:

(а+(а+(а*(а*а))))

(а+(а+((а*а)*а)))

((а+а)+((а*а)*а))

((а+а)+(а*(а*а)))

Вхідні дані

У першому рядку міститься коректний вираз, що містить не більше 25 знаків операцій.

Вихідні дані

Вивести кількість способів розстановки дужок.

Приклади