This is hard version of Calculate Factorial - 1.Only the constraints on test cases differ, rest of the question is same.

For a total of T test case, you are given an integer N, and you are asked to print its factorial modulo ( 10⁹ + 7) .

Recall that factorial is the product of integers from 1 till n.

Input:-

First line contains the number of test cases.

Second line contains the integer N.

Output:-

Print the factorial of N modulo ( 10⁹ + 7).

Constraints:-

1 <= T <= 100000

1 <= N <= 50000