Arranging teams in a programming competition

All submissions for this problem are available.
You are the organizer of a very famous programming competition. There are total n students participating in it. Before the start of the competition, all participants were asked to sit in a line. The participants sat at any positions according to their choices. You are given this initial sitting of participants by a string s of size n. Each character of string s is a lower case English alphabet from 'a' to 'z' denoting the team name of the participant.
Initially, the participant did not even take care that all the participants of same team should be sitting consecutively, continuously as a group, so that they can discuss the problems among themselves. You are annoyed to see this and want to rearrange the sitting of the participants.
Being a mathematician, you thought of following way for rearranging the students  You generate a permutation P of {1, 2, ..., n}. Then you ask the participant sitting at position i to go and stand at position P_{i}. After the rearrangement is done, you ask all the standing participants to sit down and occupy the seats. Let us take an example, say "abc" denote the current arrangement of students. Let permutation P be {2, 3, 1}. Then participant 'a' at position 1 will go and stand at position 2, participant 'b' sitting at position 2 will go to position 3 and stand there. Participant 'c' will go and stand at position 1. Finally, all the participants will sit at their position and the final rearrangement will be shown by string "cab".
You just realized that not all permutations will arrange the participants in a correct way. So, you are just wondering how many permutations P of {1, 2, , n} exist such that the rearranged sittings of the participants satisfy the requirement of team members of each team being continuous. As the answer could be large, output it modulo 10^{9} + 7.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of the each test case will contain a string s denoting the initial arrangement of the participants..
Output
For each test case, output a single integer corresponding to number of valid permutations as stated in the problem. Output your answer modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 10
 s will consist of lower case English alphabets, i.e. characters from 'a' to 'z'.
Subtasks
Subtask #1 (30 points)
 1 ≤ n, i.e. size of string s ≤ 8
Subtask #2 (70 points)
 1 ≤ n, i.e. size of string s ≤ 10^{5}
Example
Input 3 aba aaa abc Output: 4 6 6
Explanation
Example case 1. There are total 4 valid permutations. These are {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}. The invalid permutations are {1, 2, 3} and {3, 2, 1}.
Example case 2. As all the participants belong to same team. All the 6 permutations will be valid.
Example case 3. In this case, there is a single participant per team, so here also all the 6 permutations will be valid.
Author:  admin2 
Tags  admin2 
Date Added:  5072016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions