题目描述

定义于字母表 \(∑\)={\(a,b,c\)} 上的乘法表如下：

字符	a	b	c
a	\(b\)	\(b\)	\(a\)
b	\(c\)	\(b\)	\(a\)
c	\(a\)	\(c\)	\(c\)

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

对于给定的字符串 \(x= x_1x_2 \cdots x_n\)，计算有多少种不同的加括号方式，使由 \(x\) 导出的加括号表达式的值为 \(a\)。

格式

输入格式

第一行中给出一个字符串 \(x\)。

输出格式

输出一 行包含一个整数，表示计算出的加括号方式数。

样例1

样例输入1

bbbba

样例输出1

6

限制

\(100\%\)的数据：\(n ≤20\)。