Problem code: PPERM
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 ith integer is the Xth 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.
The first line contains a single integer T, denoting the number of test cases. Then T lines follow, each containing a single integer N.
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.
Input: 4 1 2 3 4 Output: 1 2 6 18
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.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.