Prime Permutations

All submissions for this problem are available.
A permutation of N distinct integers between 1 and N, both inclusive, is called a prime permutation of size N iff  for all i between 1 and N, the following condition holds:
The i^{th} integer is the X^{th} smallest integer in the first i integers, where X is either 1 or a prime number.
Your task is to find out how many prime permutations are there of size N.
Input
The first line contains a single integer T, denoting the number of test cases. Then T lines follow, each containing a single integer N.
Output
For each test case, output a single line containing the number of prime permutations of size N. Since the answers can be very large, output each answer modulo 1,000,000,007.
Example
Input: 4 1 2 3 4 Output: 1 2 6 18
Constraints:
1 ≤ T ≤ 500,000
1 ≤ N ≤ 5,000,000
Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.
WARNING! Large I/O files. Use fast I/O methods.
Author:  yellow_agony 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/PPERM 
Tags  cook26 easy sieve yellow_agony 
Date Added:  7062012 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
some more testcases please
for 5000000 its : 965379749
more test cases plsss
please make the solution to
How come some solutions are
Someone Please explain the
Not bad, not bad. The