Albocede DNA (Large)

The DNA of the Albocede species is made of four nucleotides, written a, b, c, and d. Two Albocedes may carry different nucleotide orders, but every Albocede DNA sequence obeys all of these rules.

• It contains at least one a, at least one b, at least one c, and at least one d.
• Every a comes before every b, every b comes before every c, and every c comes before every d.
• The number of as equals the number of cs.
• The number of bs equals the number of ds.

For example, abcd and aabbbccddd are valid Albocede DNA sequences, while acbd, abc, and abbccd are not.

The Albocede-n is a species that evolved from the Albocede. The DNA sequence of an Albocede-n is one or more valid Albocede DNA sequences written one after another. For example, abcd and aaabcccdaabbbccdddabcd are valid Albocede-n DNA sequences. A valid Albocede-n DNA sequence is not always a valid Albocede DNA sequence.

An expedition brought back a sequence $S$ made only of a, b, c, and d. Count the subsequences of $S$ that are valid Albocede-n DNA sequences. A subsequence is a string obtained by deleting zero or more characters and keeping the order of the rest. Two choices of positions count separately even when they produce the same string. The count can be very large, so report it modulo $10^9 + 7$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string $S$ made only of the characters a, b, c, and d.

Limits

• $1 \le T \le 20$
• $1 \le |S| \le 500$

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the answer for that test case.