here's the question statement-

Alice has N balls arranged in a single line. The balls are either red(R), blue(B), green(G) or white(W). They can be represented a string S. Every character of the string is either R, B, G or W.

In the beginning, also there are no two balls of the same color side by side (except white ball). For example GGWWB is not a valid string because there are two green balls together. But GWWB is a valid string as there are no two balls of same color side by side except white balls.

Alice needs to paint all the white balls in one of the other three colors in a way that there are no two balls of the same color side by side.

How many ways Alice can paint the balls? Print the solution modulo 1000000007 (109 + 7).

Input The first line contains the number of test cases T (1 ≤ T ≤ 1000). In each line of the test cases, there will be a string S of length N (1≤ N ≤ 100000).

Total number of character in the input file will be less than 5*10^6.

Output For each test case, print the case number and the answer to the problem.

Sample Input 2 WWG GWGWB

Output

Case 1: 4 Case 2: 2

Explanation for case 1: The four valid ways to color the balls are RBG, BRG, GRG, GBG.

problem link- https://algo.codemarshal.org/contests/icpc-dhaka-preli-18/problems/H