Задачи командного чемпионата

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

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

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

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

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

В первой строке входного файла содержится корректное выражение, содержащее не более 25 знаков операций.

В выходной файл вывести одно число – количество способов расстановки скобок.

а+а+а*а*а

4