Let there be three groups of people waiting to attend a meeting. There are $\textbf N$ people in each group. There is a round table in the meeting room. The coordinator wants them to sit in a way around the table that there will be no two-person of the same group sitting adjacently. He decides to make such an arrangement step by step.
Step 1: In this step there will be
$\textbf N$chairs and people of the first group will enter the room and sit adjacently.Step 2: People of second group will enter the room. The coordinator will provide
$\textbf N$more chairs. Note that first group has entered and sat already. Second group of people will take seat in a way that there will be no two person of the same group sitting adjacently.Step 3: People of third group will enter the room. The coordinator will provide
$\textbf N$more chairs. Note that first and second group has entered and sat already. Third group of people will sit around the table in a way that there will be no two person of the same group sitting adjacently.
When a group enters the room and sits they will not alter the order of sitting arrangement of previous group.
You will be given the number of people in each group. Your task is to calculate how many ways they can sit around the table. Two ways are considered same if rotating one arrangement any number of times can form the other arrangement.
Input
First line of the input file will contain a single positive integer $\textbf{T}$ $(1\leq T \leq 10^{6})$ which denotes the number of test cases.
Each of the next $\textbf T$ lines will contain one integer $\textbf N$ $(1\leq N \leq 10^{7})$ where$\textbf N$ = Number of people in each group.
Output
For each test case print the number of ways they can sit in a line$\mod (10^{9}+7)$
Sample
| Input | Output |
|---|---|
2 1 2 | 2 24 |
