Albocede DNA (Small)

The DNA of the alien species Albocede is made of four nucleotides: a, b, c, and d. Sequences differ between individuals, but every Albocede DNA sequence obeys all of these rules:

• Each of a, b, c, and d appears at least once.
• 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. acbd, abc, and abbccd are not.

The Albocede-n is a species that evolved from the Albocede. An Albocede-n DNA sequence is one or more valid Albocede DNA sequences concatenated end to end. For example, abcd and aaabcccdaabbbccdddabcd are valid Albocede-n DNA sequences. A valid Albocede-n DNA sequence is not necessarily 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 formed by choosing positions of $S$ and keeping their order, and two different sets of positions count as two different subsequences even when they spell the same string. The answer 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 a string $S$ made only of the characters a, b, c, and d.

Limits

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

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.