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