|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||0||0||0||0.000%|
Soundex is a phonetic algorithm for transforming a string into a code, which is always a letter followed by three digits. The purpose is that strings with a different spelling but similar pronounciation will be transformed into the same code. The transformation rules are as follows:
ware ignored. The vowels,
y, are not encoded.
ware also replaced by a single digit. Two letters with the same digit separated by a vowel will appear as the digit twice.
Some example transformations are:
rupertare transformed to R163.
baawwwwwis transformed to B000.
hoppis transformed to H100. The first letter of the string always becomes the first letter in the code, even if it is a vowel or
ratatatais transformed to R333, because the vowel between each pair of
t(3) forces the digit to be repeated.
yhhhwthwhtwhthwhwthis transformed to X300. All occurrences of
ware ignored, leaving only one
3in the code.
bbpbis transformed to B100. The first
bis kept separate from the last three
b’s. The remaining
b’s are consecutive and are replaced with one digit.
Your evil friend Halvor has noticed that a lot of different words will give the same soundex code. For example, the strings
robnew and 73908 other strings with 6 or less letters will be converted to the code R150. This makes him very curious, and he wants to know the number of strings of the a given length or shorter that will be converted to the same soundex code. Naturally, he wants you to write a computer program to accomplish this task. Your friend does not care about upper or lower case, so
aa etc are considered to be equal strings and should only be counted once.
The first line of input contains a single integer T, the number of test cases to follow. Each test case begins with a line containing a string S and an integer number L. S represents a soundex code, and consists of one uppercase letter followed by three digits. L represents the maximum length of the original string which is converted into the given soundex code.
zare considered. No
åor other non-English characters are to be used.
For each test case output one line containing a single number, the number of strings of length L or less having the soundex code S. This number can be large, so output it modulo 1,000,000,007.
3 A300 2 R150 6 X123 1
2 73912 0