알보시드 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 서열이 몇 개인지 세어라. 부분 수열은 순서를 그대로 두고 문자를 0개 이상 지워서 얻는 문자열이다. 고른 위치가 다르면 결과 문자열이 같아도 서로 다른 부분 수열로 센다. 답이 매우 클 수 있으니 $10^9 + 7$으로 나눈 나머지를 구한다.

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

제한

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

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