Challenge
Challenge
Problem
Solutions
Submissions
Challenge Points: 10
Level: EasyGiven a positive integer n, consider all permutations of the numbers 1, 2, ..., n.
We call a permutation valid when every prime number in the permutation sits at an index that is prime (indices use 1-based numbering). Non-prime numbers may occupy non-prime indices.
Return the total number of valid permutations modulo 10^9 + 7.
(Recall: a prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.)
Input: n = 4
Output: 4
Explanation:
Primes in 1..4 are {2,3} (2 primes), non-primes are {1,4} (2 numbers). Valid permutations = 2! (arrange primes at prime indices) × 2! (arrange non-primes at remaining indices) = 2 × 2 = 4.
Input: n = 6
Output: 36
Explanation:
Primes: {2,3,5} (3 primes), non-primes: {1,4,6} (3 numbers). Valid permutations = 3! × 3! = 6 × 6 = 36.
Accepted:
Submission:
Report an issue
Code
You need toto run or submitYou need toto run or submit
Test Case
Test Result