Given f(n)= [((1^2)x(nC1)^2) + ((2^2)x(nC2)^2) + ((3^2)x(nC3)^2) + ...... + ((n^2)x(nCn)^2)]%MOD.

Let there are k primes between 1 and n(inclusive) namely p1,p2,p3..pk.Your task is to find sum where: sum=(f(p1) + f(p2) + f(p3) +...+f(pk))%MOD

Input:

t:testcases

for each test case n is given

Output:

Print the value of sum.

Constraints:

1<=t<=100

1<=n<=10^6

MOD: 10^9 + 7