게으른 철자 대회 (큰 입력)

철자 대회에 나온 참가자는 목표 단어 $W$의 철자를 말한다. 참가자가 말한 단어 $A$는 길이가 $W$와 같고, 모든 $i$에 대해 $A$의 $i$번째 글자가 $W$의 $i-1$번째, $i$번째, $i+1$번째 글자 가운데 하나와 같으면 정답으로 인정한다. $W$에 $0$번째 글자는 없으므로 $A$의 첫 글자는 $W$의 첫 글자나 두 번째 글자와 같아야 한다. 마찬가지로 $A$의 마지막 글자는 $W$의 마지막 글자나 그 바로 앞 글자와 같아야 한다. 목표 단어 자신은 언제나 정답으로 인정한다.

대회를 준비하면서 목표 단어마다 서로 다른 정답 단어가 몇 개인지 세어야 한다. 이 수가 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

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

제한

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

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

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