Our warmest thanks to Clive Fraser for this problem!
In this problem we are interested in strings of lower case letters and in the number of vowels contained in the string. The characters in the
string will be chosen from the 26 lower case letters and no others. The vowels are the characters {a, e, i, o, u}. The number of vowels in
the string is the number of characters in the string which are one of the 5 vowels. For a string of length N the number of vowels can be
any number between 0 and N inclusive. We are particularly interested in strings where the number of vowels is a prime number i.e. one of
{2, 3, 5, 7, 11, 13, ...}.
In the problem you will be given two strings of the same length N. The first will be lexicographically smaller than the second. You are to
consider the range of all strings of length N, in lexicographic order, from the first string to the second string, inclusive. You are
required to find the number of these strings which contain a prime number of vowels. As the answer can be very large, you are asked to give it
modulo 1000000007 (10^9 +7).
Consider a small example where N = 6. The first and second strings are aabbal and aabbbb. There are 15 strings in this range where the
number of vowels is a prime number. The diagram below lists these strings and the number of vowels in each.
aabbal 3
aabbam 3
aabban 3
aabbap 3
aabbaq 3
aabbar 3
aabbas 3
aabbat 3
aabbav 3
aabbaw 3
aabbax 3
aabbay 3
aabbaz 3
aabbba 3
aabbbb 2
Not surprisingly, in such a small example there is not much variation. In particular, there is no string in this range which contains 5
vowels (another prime number). An example of such a string (but not in the given range) would be abaoio.
You will be given a number of sets of test data, with strings of varying length N. The value of N will never exceed 150.
Input/Output description: The first line of the input data contains a single integer T, the number of test cases. Each test case covers
3 separate lines. The first line contains a single integer N, the length of the strings. The second line contains the first string of
length N. The third line contains the second string of length N. You are asked to calculate the number of strings in the given range where
the number of vowels in the string is a prime number. Give the answer modulo 1000000007. Combine all answers into a single string, separated
by single spaces.
Example:
input:
6
2
kx
va
3
eze
sxo
4
mekj
zqwe
6
aabbal
aabbbb
8
dsegcksr
lojawdsa
12
hlfdybiyalbx
kgonjdhxkyjs
answer:
10 774 35919 15 411439637 718554152