Problem C

Beaver Bindu has N cupcakes. Each cupcake has one of three possible colors. In this problem we will represent the colors by uppercase letters 'A', 'B', and 'C'. Two cupcakes of the same color are indistinguishable. You are given a String cupcakes consisting of exactly N characters. Each character in cupcakes gives the color of one of Bindu's cupcakes.

Bindu has N friends, sitting around a round table. She wants to give each friend one of the cupcakes. Moreover, she does not want to give cupcakes of the same color to any pair of friends who sit next to each other.

Let X be the number of ways in which she can hand out the cupcakes to her friends. As X can be very large, compute and return the value (X modulo 1,000,000,007).

The first line contains one integer T(1 ≤ T ≤ 60)—the number of test cases. Each of the next T lines contains one string. Each string will contain between 3 and 50 characters, inclusive. Each character in the string will be either 'A', 'B', or 'C'.

For each test case. Print a single number X — the number of ways in which she can hand out the cupcakes to her friends.

3
ABAB
ABABA
ABABABABABABABABABABABABABABABABABABABABABABABABAB

2
0
2

计算机学院大学生程序设计竞赛（2014’12）