UCPC Garland#13080

UCPC Garland

4.5 seconds
256 megabytes

The organizers of UCPC are decorating the competition hall with a long garland of lamps shaped like letters. The garland forms a string of length consisting of uppercase Latin letters: the -th lamp shows the letter s_i. Each lamp must be turned on in one of three colors: blue, yellow, or white.

Of course, the organizers' favorite word is UCPC. An occurrence of the word UCPC in the garland is a choice of four lamps at positions i_1 < i_2 < i_3 < i_4 that show the letters U, C, P, C respectively (the chosen lamps do not necessarily have to be adjacent). The coloring of an occurrence is the sequence of colors of the lamps i_1, i_2, i_3, i_4 in exactly that order.

A coloring of the entire garland is called consistent if all occurrences of the word UCPC have the same coloring. In other words, no matter which occurrence of the word UCPC a viewer reads in the garland, they will always see the same sequence of colors. In particular, if UCPC does not occur in the garland at all, then any coloring is consistent.

Count the number of consistent colorings of the garland. Two colorings are considered different if at least one lamp has a different color in them. Since the answer can be large, output it modulo .

The organizers are considering several garlands, and you need to answer this question for each of them.

Input

The first line contains an integer (1 \le t \le 10^6) — the number of garlands.

Each of the next lines contains a string (1 \le |s| \le 10^6, where is the length of the string ) — the garland. It is guaranteed that the garland consists of uppercase Latin letters.

The total length of all strings does not exceed 10^6.

Output

For each garland, output on a separate line a single integer — the number of its consistent colorings modulo .

Examples

Example 1

Loading
Loading

Note

In the first example garland, the word UCPC occurs four times, at positions (1,2,3,4), (1,2,3,6), (1,2,5,6), and (1,4,5,6). Lamp is the second letter of the last occurrence and the fourth letter of the first one, so both letters C of the word must have the same color. Hence all lamps with the letter C share one common color, and both lamps with the letter P share one common color. Together with the color of lamp , this gives 3^3 = 27 consistent colorings.

In the second example garland, no lamp can simultaneously be the second and the fourth letter of an occurrence, so the two letters C of the word can have different colors: lamps share one common color, lamps — one common color, lamps — one common color, and lamps — one common color, giving 3^4 = 81 colorings.

In the third example garland, the word UCPC does not occur at all, so all 3^3 = 27 colorings are consistent.