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$

70% Solution Ratio

sakib_muhitEarliest,

AungkurFastest, 0.3s

sayeef006Lightest, 90 MB

abid1729Shortest, 245B