Дужки

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

(a+(a+(a*(a*a))))

(a+(a+((a*a)*a)))

((a+a)+((a*a)*a))

((a+a)+(a*(a*a)))