알보세데 DNA (스몰)

알보세데라는 외계 종족의 DNA는 a, b, c, d 네 종류의 뉴클레오타이드로 이루어진다. 개체마다 서열은 다르지만, 모든 알보세데의 DNA 서열은 다음 규칙을 전부 만족한다.

• a, b, c, d가 각각 적어도 한 번씩 나온다.
• 모든 a는 모든 b보다 앞에 오고, 모든 b는 모든 c보다 앞에 오며, 모든 c는 모든 d보다 앞에 온다.
• a의 개수와 c의 개수가 같다.
• b의 개수와 d의 개수가 같다.

예를 들어 abcd와 aabbbccddd는 올바른 알보세데 DNA 서열이고, acbd, abc, abbccd는 아니다.

알보세데-n은 알보세데에서 진화한 종족이다. 알보세데-n의 DNA 서열은 올바른 알보세데 DNA 서열 하나 이상을 순서대로 이어 붙인 것이다. 예를 들어 abcd와 aaabcccdaabbbccdddabcd는 올바른 알보세데-n DNA 서열이다. 올바른 알보세데-n DNA 서열이 반드시 올바른 알보세데 DNA 서열인 것은 아니다.

탐사에서 a, b, c, d로만 이루어진 서열 $S$를 하나 가져왔다. $S$의 부분 수열 중 올바른 알보세데-n DNA 서열인 것이 몇 개인지 세어라. 부분 수열은 $S$에서 위치를 골라 원래 순서대로 이어 만든 것이고, 고른 위치 집합이 다르면 만들어진 문자열이 같더라도 서로 다른 부분 수열로 센다. 답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 a, b, c, d로만 이루어진 문자열 $S$가 주어진다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 테스트 케이스의 답이다.