게으른 철자 맞히기 대회

게으른 철자 맞히기 대회에서 참가자에게 철자를 말해야 할 목표 단어 W가 주어진다. 참가자의 답 단어 A는 목표 단어와 길이가 같고, A의 길이 범위에 있는 모든 i에 대해 A의 i번째 글자가 W의 i번째, (i-1)번째 또는 (i+1)번째 글자 중 하나이면 허용된다. (W의 0번째 글자는 존재하지 않으므로, A의 첫 글자는 W의 첫 글자 또는 두 번째 글자와 일치해야 한다. 마찬가지로 A의 마지막 글자는 W의 마지막 글자 또는 끝에서 두 번째 글자와 일치해야 한다.) 목표 단어 자체는 항상 허용되는 답 단어임에 유의한다.

여러분은 Lazy Spelling Bee를 준비하고 있으며, 각 목표 단어에 대해 서로 다른 허용되는 답 단어가 몇 개인지 구해 달라는 요청을 받았다. 이 수는 매우 클 수 있으므로, 1000000007 ($10^{9}$ + 7)로 나눈 나머지를 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ 각 문자열의 길이 ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ 각 문자열의 길이 ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 소문자 영어 알파벳 문자만으로 이루어진 문자열 하나가 있는 한 줄로 구성된다(a부터 z까지).

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 서로 다른 허용되는 답 단어의 수를 $10^{9}$ + 7로 나눈 나머지이다.

예제 케이스 #1에서 허용되는 답 단어는 aa, ag, ga, gg이다.

예제 케이스 #2에서 허용되는 답 단어는 aa뿐이다.