Question
Equal Vowel Power Subsequences
You are given a string of length KaTeX can only parse string typed expression, consisting only of lowercase English letters. Your task is to count the number of subsequences such that:
-
Each vowel (KaTeX can only parse string typed expression) appears the same number of times in the subsequence.
-
This common frequency of the vowels is a power of 2, i.e., KaTeX can only parse string typed expression.
Consonants may appear any number of times (including zero).
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Output
Print a single integer — the number of such subsequences modulo KaTeX can only parse string typed expression.
Example
Input
7
aeibcou
Output
4
Explanation
There is exactly one occurrence of each vowel → KaTeX can only parse string typed expression (which is a power of 2).
We must pick all five vowels, and we have one consonant (KaTeX can only parse string typed expression and KaTeX can only parse string typed expression are consonants). Each consonant can either be included or excluded independently.
The valid subsequences are:
aeiou
aeibou
aeicou
aeibcou
7
aeibcou
Output
4
Explanation
There is exactly one occurrence of each vowel → KaTeX can only parse string typed expression (which is a power of 2).
We must pick all five vowels, and we have one consonant (KaTeX can only parse string typed expression and KaTeX can only parse string typed expression are consonants). Each consonant can either be included or excluded independently.
The valid subsequences are:
aeiou
aeibou
aeicou
aeibcou