32345번 - 혼긱대학교

문제

홍익대학교의 영어 이름은 hongik university이다. 하지만 읽는 사람에 따라 이를 hong/ik으로 발음하지 않고, hon/gik으로 발음해 혼긱대학교가 되는 웃지 못할 상황이 종종 벌어지곤 한다.

자음이 앞 모음에 붙느냐, 뒤 모음에 붙느냐에 따라 단어의 발음이 다른 것을 신기하게 여긴 동현이는 비슷한 상황인 영어 단어들을 조사해서 발음이 얼마나 다양하게 될 수 있는지를 알아보려 한다. 하지만, 영어를 잘 못하는 동현이는 아래의 규칙에 따라서만 발음을 파악한다.

• 영어 모음은 a, e, i, o, u 5개이며, 자음은 모음을 제외한 나머지 21개의 알파벳이다.
• 1개의 모음에 0개 이상의 자음이 앞뒤로 붙어서 하나의 음이 되고, 음들이 모여서 단어의 발음이 된다.
  • 예) h, o, n, g, i, k → hong, ik → hongik
• 자음과 자음, 자음과 모음은 인접했을 때만 한 음으로 모일 수 있다.
• 음에 구성된 알파벳의 개수, 구성, 순서가 다른 경우 다른 음으로 취급한다.
  • 예) ab와 abb, ba는 모두 다른 음이다.
• 주어진 단어의 알파벳을 각각 1회씩 사용해서 발음을 만들어야 한다.
• 각 음의 구성이 다른 경우 단어의 발음이 다른 것으로 생각한다.

이와 같은 규칙에 따라 단어들이 발음될 수 있는 경우의 수를 출력해 보자.

입력

첫째 줄에 테스트 케이스의 개수 \(T\)가 주어진다. \((1 ≤ T ≤ 100,000円)\)

둘째 줄부터 \(T\)개의 줄에 걸쳐, 알파벳 소문자로 이루어진 단어 \(S\)가 주어진다. \((1 ≤ |S| ≤ 300,000円)\)

모든 테스트 케이스에 대해 단어의 길이의 합은 \(1,000円,000円\) 이하이다.

출력

매 줄마다, 각 테스트 케이스에서 단어의 발음의 경우의 수를 출력한다.

이때 경우의 수가 너무 커질 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력하자.

만약 모음이 없어서 발음 할 수 없을 경우 -1을 출력한다.

제한

힌트

hongik의 경우 ho/ngik , hon/gik , hong/ik 3가지로 발음할 수 있다.