Counting Soundex Strings

Soundex is a phonetic algorithm that turns a string into a code. A code is always one letter followed by three digits. Strings that are spelled differently but sound alike get the same code. The rules are these.

• The first letter of the string becomes the first letter of the code.
• Every consonant after the first letter is replaced by a digit.
  • b, f, p, v become 1
  • c, g, j, k, q, s, x, z become 2
  • d, t become 3
  • l becomes 4
  • m, n become 5
  • r becomes 6
• h and w are ignored. The vowels a, e, i, o, u and y produce no digit, but they separate the letters around them.
• Two or more adjacent letters with the same digit become a single digit. Letters with the same digit separated only by h or w also become a single digit. Two letters with the same digit separated by a vowel give that digit twice.
• Repeat the previous rule until no repeated digit can be merged.
• If fewer than 3 digits remain, pad the right side with zeros. If more than 3 digits remain, drop everything after the third digit.

The first letter only supplies the letter of the code. It never merges with the digits that follow it.

Some transformations:

• robert and rupert both become R163.
• baawwwww becomes B000.
• hopp becomes H100. The first letter of the string always becomes the first letter of the code, even when it is a vowel or h or w.
• ratatata becomes R333, because the vowel between each pair of t (3) forces the digit to repeat.
• yhhhwthwhtwhthwhwth becomes Y300. Every h and w is ignored, so a single 3 is left.
• bbpb becomes B100. The first b gives the letter of the code, and the three remaining letters all carry digit 1 and stand next to each other, so they collapse into one digit.

Many different words share one code. For example rhhhbm, rubeno, rpowam, robnew and 73908 further strings of 6 letters or fewer all become R150. Given a code and a maximum length, count the strings of that length or shorter that produce the code. Case does not matter, so AA, Aa and aa are the same string and are counted once.

The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains a string $S$ and an integer $L$ separated by a space. $S$ is a soundex code, one uppercase letter followed by three digits. $L$ is the largest allowed length of the original string.

• $0 < T \le 100$
• $0 < L \le 1000$
• The original strings use only the letters a to z.
• Case is ignored. Two strings of the same length whose letters match position by position are the same string.
• Every given code is legal: a nonzero digit never follows a zero digit, and every digit is between 0 and 6.

For each test case print one line with the number of strings of length $L$ or less whose soundex code is $S$. This number can be large, so print it modulo 1000000007.