게으른 스펠링 비 (스몰)

게으른 스펠링 비에서는 참가자에게 목표 단어 $W$를 철자로 말하게 한다. 참가자가 답한 단어 $A$는 다음 두 조건을 모두 만족할 때 인정된다.

• $A$의 길이가 $W$의 길이와 같다.
• 모든 $i$에 대해 $A$의 $i$번째 글자가 $W$의 $i-1$번째, $i$번째, $i+1$번째 글자 가운데 하나와 같다.

$W$에 $0$번째 글자는 없으므로 $A$의 첫 글자는 $W$의 첫 글자나 두 번째 글자와 같아야 한다. 마지막 글자도 마찬가지로 $W$의 마지막 글자나 끝에서 두 번째 글자와 같아야 한다. 목표 단어 자체는 언제나 인정되는 답이다.

목표 단어마다 인정되는 서로 다른 답 단어가 몇 개인지 구하라. 이 수가 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 소문자 알파벳(a부터 z까지)으로만 이루어진 문자열이 하나씩 주어진다.

제한

• $1 \le T \le 100$
• 각 문자열의 길이는 $1$ 이상 $5$ 이하이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 인정되는 서로 다른 답 단어의 개수를 $10^9 + 7$로 나눈 나머지이다.

목표 단어가 ag이면 인정되는 답은 aa, ag, ga, gg의 네 개다. 목표 단어가 aa이면 인정되는 답은 aa 하나뿐이다.