There are three types of beads namely A,B and C. Now we require to make a garland out of it with the constraints that no two adjacent beads should be of the same type. Obviously it follows that the first and last beads should be of different types as well.
Given a string representing the types of beads you are asked to return the different types of garlands you can make modulo 1,000,000,007.
The test file consists of multiple cases. Each case consists of a single line containing the string. Read till EOF.
Print the answer of separate lines for each test case.
3 <= Length of input string <= 50
Number Of Test cases < 100
Sample Test Cases
Case 1: ABAB or BABA
Case 2: ABC or ACB or BAC or BCA or CAB or CBA
Case 3: In all permutations, two As are bound to come together.
Problem Setter : Shradha Chhaparia