乘法表问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

定义于字母表S={a,b,c}上的乘法表如下:

依此乘法表,对任一定义于S上的字符串,适当加括号后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个算法,对任一定义于S上的字符串x= x1x2……xn ,计算有多少种不同的加括号方式,使由x 导出的加括号表达式的值为a。
对于给定的字符串x= x1x2……xn ,计算有多少种不同的加括号方式,使由x 导出的加括号表达式的值为a。

Input

输入数据的第1 行中给出一个字符串(长度不超过20)。

Output

将计算结果输出。第1 行中的数是计算出的加括号方式数。

Sample Input

bbbba

Sample Output

6

Hint

 

Source