提示: 欢迎访问OurACM平台。
Problem 1435 Multiplication Table

Accept: 85    Submit: 123
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Define a special multiplication table based on the alphabet ={a,b,c} as follows.



According to the multiplication table above, we can form an expression by adding parenthesis into the string based on the alphabet properly. For instance, x=bbbba is a string based on the alphabet . (b(bb))(ba) is one of its expressions after adding some parenthesis. The result of this expression should be a, according to the multiplication table. It is obvious that different ways of adding parenthesis can have different values. Given a string based on the alphabet , your task is to find the number of ways of adding parenthesis that can form an expression whose result is a.

Input

There are several test cases. Each case contains only one line with a string.The length of each string would not exceed 200.

Output

Output one integer indicating the result you have computed.

Sample Input

bbbba

Sample Output

6

Source

FZU 2006 Summer Training II

Submit  Back  Status  Discuss