Untitled

A couple of friends decided to play an anagram-finding word game. The point of the game is to find all the anagrams of a given word. Unfortunately, the friends are not fluent in English, so, instead of finding all the English words, they decided to look for all the well-structured words. We say that a word is well-structured if it:

starts with a consonant;
does not contain two consecutive vowels;
does not contain two consecutive consonants.
Assume that the letters AEIOU are vowels, and that all other letters are always consonants. Please note, that Y is treated as a consonant.

For example, the following words are well-structured:

PUTOR,
RUME,
TABEK,
BABABAB,
BABABA,
YAMAR.
However, the following words are not well-structured:

ABAR (does not start with a consonant),
BAAR (contains two consecutive vowels),
KAKKE (contains two consecutive consonants),
AARO (does not start with a consonant, and also contains two consecutive vowels),
BOARD (contains two consecutive vowels and also two consecutive consonants).
Please note that a word does not have to be a valid English word in order to be well-structured, and that there are valid English words that are not well-structured.

Count the number of well-structured words that can be obtained by rearranging the letters of the input word. Since the answer can be very large, provide it modulo 1,000,000,007 (109 + 7).

Write a function:

def solution(S)

that, given a string S, returns the number of well-structured words (modulo 1,000,000,007) that can be obtained by rearranging letters of S.

Examples:

1. Given S = "BAR", your function should return 2, because there are two well-structured words that can be formed from those letters:

BAR,
RAB.
2. Given S = "AABB", your function should return 1, because there is only one well-structured word that can be formed from those letters:

BABA.
3. Given S = "AABCY", your function should return 6, because there are six well-structured words that can be formed from those letters:

BACAY,
BAYAC,
CABAY,
CAYAB,
YABAC,
YACAB.
4. Given S = "AAAB", your function should return 0, because there are no well-structured words that can be formed from those letters.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..30];
string S is made only of uppercase letters (A−Z).