P16509 [GKS 2015 #B] Albocede DNA

The DNA of the Albocode alien species is made up of $4$ types of nucleotides: a, b, c, and d. Different Albocedes may have different sequences of these nucleotides, but any Albocode's DNA sequence obeys all of the following rules: * It contains at least one copy of each of a, b, c, and d. * All as come before all bs, which come before all cs, which come before all ds. * There are exactly as many 'a's as 'c's. * There are exactly as many 'b's as 'd's. For example, abcd and aabbbccddd are valid Albocode DNA sequences. acbd, abc, and abbccd are not. The Albocode-n is an evolved species of Albocode. The DNA sequence of an Albocode-n consists of one or more valid Albocode DNA sequences, concatenated together end-to-end. For example, abcd and aaabcccdaabbbccdddabcd are valid Albocode-n DNA sequences. (Observe that a valid Albocode-n DNA sequence is not necessarily also a valid Albocode DNA sequence.) From one of your alien expeditions, you retrieved an interesting sequence of DNA made up of only as, bs, cs, and ds. You are interested in how many of the different subsequences of that sequence would be valid Albocode-n DNA sequences. (Even if multiple different selections of nucleotides from the sequence produce the same valid subsequence, they still all count as distinct subsequences.) Since the result may be very large, please find it modulo 1000000007 ($10^9+7$).

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

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and $y$ is the output of the xth test case.

### Limits $1 \le T \le 20$. **Small dataset (Test Set 1 - Visible)** $1 \le \text{length of S} \le 50$. **Large dataset (Test Set 2 - Hidden)** $1 \le \text{length of S} \le 500$.