A bank vault has n numbered slots, labeled 1 through n, and exactly n uniquely numbered deposit boxes, also labeled 1 through n. The vault manager must place all n boxes into the n slots, one box per slot, following a security rule: whenever a slot's number is a prime number, the box placed in it must also carry a prime number (boxes with a non-prime number, including box 1, may go into any slot whose number is not prime).
Count the number of ways to fill all n slots that satisfy this rule, modulo 1,000,000,007.
A single line containing one integer n.
Print a single integer: the number of valid ways to fill the vault, modulo 1,000,000,007.
Example 1
Input
5
Expected
12
Explanation
The primes from 1 to 5 are 2, 3, and 5, so p = 3 prime slots and 2 non-prime slots (1 and 4). The 3 prime boxes {2,3,5} can be arranged among the 3 prime slots in 3! = 6 ways, and the 2 non-prime boxes {1,4} among the 2 non-prime slots in 2! = 2 ways, giving 6 * 2 = 12 total arrangements.
Example 2
Input
1
Expected
1
Explanation
There are no primes from 1 to 1 (p = 0), so all n = 1 boxes are non-prime and there is exactly one way to place the single box into the single slot: 0! * 1! = 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →