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

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

输入数据的第 1 行中给出一个字符串。

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