Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer&nbsp;is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers&nbsp;both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

&nbsp;
Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.


Example 2:

Input: n = 100
Output: 682289015


&nbsp;
Constraints:


	1 &lt;= n &lt;= 100


class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        primes = set()
        for i in range(2,n+1):
            if all(i%p != 0 for p in primes):
                primes.add(i)
        M = 10**9 + 7
        def fact(k):
            res = 1
            for i in range(2,k+1):
                res = (res*i)%M
            return res
        return fact(len(primes))*fact(n-len(primes))%M
class Solution {
     long mod = (long)(1e9+7);
    public int numPrimeArrangements(int n) {
        if(n==1){
            return 1;
        }
     
        boolean[] arr = new boolean[n+1];
        Arrays.fill(arr,true);
        arr[0]=false;
        arr[1]=false;
        
        for(int i=2;i<=Math.sqrt(n);i++){
            
            for(int j=i*i;j<=n;j+=i){
                if(arr[i]==false){
                    continue;
                }
                arr[j]=false;
            }
            
        }
       long prime = 0;
        long notPrime=0;
        for(int k=1;k<arr.length;k++){
            if(arr[k]==true){
                prime++;
            }
            else{
                notPrime++;
            }
        }

       long x = factorial(prime)%mod;
       long y = factorial(notPrime)%mod;
       long t = (x*y)%mod;
        return (int)t ;
        
    }
 
    public long factorial(long i){
        if(i<=1){
            return i;
        }
        return (i*(factorial(i-1)%mod))%mod;
    }
}
class Solution {
public:
    bool isPrime(int x) {
        if(x <= 3) return x > 1;
        if(x % 2 == 0) return false;
        
        for(int i = 3; i <= sqrt(x); i += 2) {
            if(x % i == 0) return false;
        }
        return true;
    }
    
    int fact(int x) {
        if(x <= 1) return 1;
        return ((long long)(x) * fact(x - 1)) % 1000000007;
    }
    
    int numPrimeArrangements(int n) {
        int c = 0;
        for(int i = 1; i <= n; ++i) {
            c += isPrime(i);
        }
        return ((long long)(fact(n - c)) * fact(c)) % 1000000007;
    }
};
/**
 * @param {number} n
 * @return {number}
 */

var findNoOfPrimes = function(n){
    let isPrime = new Array(n+1).fill(true);

    let count =0;

    for(let i=2; i<n;i++){
        for(let j=i;j<=n;j++){
            isPrime[j*i]= false;
        }
    }

    isPrime.forEach(prime=> {
        if(prime){
            count++
        }
    })

    return count-2;
}

var factorial = function(num){
    let modulo = Math.pow(10,9) +7;

    if(num<=0)
        return 1;

    return (BigInt(num) * BigInt(factorial(num-1)))%BigInt(modulo) ;
}

var numPrimeArrangements = function(n) {

    let modulo = BigInt(Math.pow(10,9) +7);

    let count = findNoOfPrimes(n);

    let factorialPrime = factorial(count);

    let factorialComposite = factorial(n-count);

    return (BigInt(factorialPrime)*BigInt(factorialComposite))% (modulo);
};
Prime Arrangements