시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 23 | 16 | 7 | 87.500% |
The DNA of the Albocede 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 Albocede's DNA sequence obeys all of the following rules:
a
, b
, c
, and d
.a
s come before all b
s, which come before all c
s, which come before all d
s.'a'
s as 'c'
s.'b'
s as 'd'
s.For example, abcd
and aabbbccddd
are valid Albocede DNA sequences. acbd
, abc
, and 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, abcd
and 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 a
s, b
s, c
s, and d
s. 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 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.
5 abcd aaaabcd aaaabbccd abcdabcdaabccd b
Case #1: 1 Case #2: 4 Case #3: 28 Case #4: 71 Case #5: 0
Contest > Google > Google's Coding Competitions > Google APAC 2016 University Graduates Test > Round B APAC Test 2016 D1번
Contest > Google > Kick Start > Google Kick Start 2015 > Round B D1번