Step 1: First group can be sitted in $\textbf (N-1)!$
different ways. (Why?)
Step 2: Second group of people can be sitted in $\textbf N!$
different ways to maintain the given constraint.
Step 3: Third group can choose spaces between the previous groups $2N \choose N$
to sit and maintain the constraint. They can arrange themselves in $\textbf N!$
ways.
You will need to precalculate the $(N! \mod 10^{9}+7)$
and $(\frac{1}{N!} \mod 10^{9}+7)$
for all $1<=N<=10^{7}$
. Try to precalculate the inverse modulo part in O(N).
Time Complexity: O( T + MAXN) Where MAXN = $10^7$