|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||1||1||1||100.000%|
The DNA of the Albocede alien species is made up of 4 types of nucleotides:
d. Different Albocedes may have different sequences of these nucleotides, but any Albocede's DNA sequence obeys all of the following rules:
as come before all
bs, which come before all
cs, which come before all
aabbbccddd are valid Albocede DNA sequences.
abbccd are not.
The Albocede-n is an evolved species of Albocede. The DNA sequence of an Albocede-n consists of one or more valid Albocede DNA sequences, concatenated together end-to-end. For example,
aaabcccdaabbbccdddabcd are valid Albocede-n DNA sequences. (Observe that a valid Albocede-n DNA sequence is not necessarily also a valid Albocede DNA sequence.)
From one of your alien expeditions, you retrieved an interesting sequence of DNA made up of only
ds. You are interested in how many of the different subsequences of that sequence would be valid Albocede-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 (109 + 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
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.
5 abcd aaaabcd aaaabbccd abcdabcdaabccd b
Case #1: 1 Case #2: 4 Case #3: 28 Case #4: 71 Case #5: 0