Colorful Cupcakes

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

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).

Input

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\'.

Output

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

Sample Input

3
ABAB
ABABA
ABABABABABABABABABABABABABABABABABABABABABABABABAB

Sample Output

2
0
2

Hint

 

Source

2014年山东省第五届ACM大学生程序设计竞赛