Soundex 문자열 세기

Soundex는 문자열을 코드로 바꾸는 발음 기반 알고리즘이다. 코드는 항상 알파벳 한 글자와 숫자 세 개로 이루어진다. 철자가 달라도 발음이 비슷한 문자열은 같은 코드가 된다. 변환 규칙은 다음과 같다.

• 문자열의 첫 글자가 코드의 첫 글자가 된다.
• 첫 글자 뒤의 자음은 숫자로 바꾼다.
  • b, f, p, v는 1
  • c, g, j, k, q, s, x, z는 2
  • d, t는 3
  • l은 4
  • m, n은 5
  • r은 6
• h와 w는 무시한다. 모음 a, e, i, o, u, y는 숫자를 만들지 않지만 앞뒤 글자를 갈라놓는다.
• 같은 숫자인 글자가 이어져 있으면 숫자 하나로 합친다. 사이에 h나 w만 있어도 하나로 합친다. 사이에 모음이 있으면 같은 숫자가 두 번 나온다.
• 합칠 수 있는 숫자가 남지 않을 때까지 앞의 규칙을 반복한다.
• 숫자가 세 개보다 적으면 오른쪽을 0으로 채운다. 세 개보다 많으면 네 번째 숫자부터 버린다.

첫 글자는 코드의 첫 글자가 될 뿐이고, 뒤에 오는 숫자와 합쳐지지 않는다.

변환 예시는 다음과 같다.

• robert와 rupert는 모두 R163이 된다.
• baawwwww는 B000이 된다.
• hopp는 H100이 된다. 첫 글자가 모음이든 h나 w든 그대로 코드의 첫 글자가 된다.
• ratatata는 R333이 된다. t(3) 사이마다 모음이 있어서 같은 숫자가 반복된다.
• yhhhwthwhtwhthwhwth는 Y300이 된다. h와 w를 모두 무시하면 3 하나만 남는다.
• bbpb는 B100이 된다. 첫 b는 코드의 첫 글자가 되고, 남은 세 글자는 모두 숫자 1이면서 붙어 있어서 숫자 하나로 합쳐진다.

서로 다른 여러 단어가 같은 코드를 만든다. 예를 들어 rhhhbm, rubeno, rpowam, robnew와 길이가 6 이하인 다른 문자열 73908개가 모두 R150이 된다. 코드 하나와 최대 길이가 주어질 때, 그 길이 이하이면서 주어진 코드로 바뀌는 문자열의 개수를 세는 프로그램을 작성하시오. 대소문자는 구분하지 않으므로 AA, Aa, aa는 같은 문자열이고 한 번만 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 문자열 $S$와 정수 $L$이 공백으로 구분되어 주어진다. $S$는 대문자 한 글자와 숫자 세 개로 이루어진 Soundex 코드이고, $L$은 원래 문자열의 최대 길이이다.

• $0 < T \le 100$
• $0 < L \le 1000$
• 원래 문자열은 a부터 z까지의 알파벳만 사용한다.
• 대소문자는 구분하지 않는다. 길이가 같고 각 자리의 글자가 같으면 같은 문자열이다.
• 주어지는 코드는 항상 올바르다. 0 뒤에 0이 아닌 숫자가 오지 않고, 각 자리의 숫자는 0부터 6까지이다.

각 테스트 케이스마다 Soundex 코드가 $S$이면서 길이가 $L$ 이하인 문자열의 개수를 한 줄에 하나씩 출력한다. 이 개수가 매우 클 수 있으므로 1000000007로 나눈 나머지를 출력한다.