{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Chef considers a string consisting of lowercase English alphabets *beautiful* if **all** the characters of the string are **vowels**. \n\nChef has a string $S$ consisting of lowercase English alphabets, of length $N$. He wants to convert $S$ into a *beautiful* string $T$. In order to do so, Chef does the following operation on **every** character of the string:\n- If the character is a **consonant**, change the character to its **closest vowel**. \n- If the character is a **vowel**, don\u0027t change it. \n\nChef realizes that the final string $T$ is not unique. Chef wonders, what is the total number of **distinct** *beautiful* strings $T$ that can be obtained by performing the given operations on the string $S$.\n\nSince the answer can be huge, print it modulo $10^9 + 7$.\n\nNote:\n- There are $26$ characters in the English alphabet. Five of these characters are vowels: `a`, `e`, `i`, `o`, and `u`. The remaining $21$ characters are consonants.\n- The closest vowel to a consonant is the vowel that is least distant from that consonant. For example, the distance between the characters `d` and `e` is $1$ while the distance between the characters `d` and `a` is $3$.\n- The distance between the characters `z` and `a` is $25$ and **not** $1$."}},{"title":"Input Format","value":{"format":"MD","content":"- The first line of input will contain an integer $T$ — the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains an integer $N$, denoting the length of the string $S$.\n- The second line of each test case contains a string $S$ consisting of lowercase English alphabets. "}},{"title":"Output Format","value":{"format":"MD","content":"For each test case, output the total number of **distinct** *beautiful* strings $T$ that can be obtained by performing the given operations on the string $S$, modulo $10^9 + 7$. \n"}},{"title":"Constraints","value":{"format":"MD","content":"- $1 \\leq T \\leq 1000$\n- $1 \\leq N \\leq 10^5$\n- Sum of $N$ over all test cases does not exceed $10^5$. \n"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n5\naeiou\n5\nabcde\n8\nstarters\n8\ncodechef\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n4\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n**Test case $1$:** All the characters of the string $S$ are **vowels**. Thus, none of the characters would be changed. The resulting string $T$ will be `aeiou`. \n\n**Test case $2$:**There are $2$ possible strings that can be obtained by performing the given operations on the string $S$. Those are `aaaee` and `aaeee`. \n\n\n\n"}}]}