## Algorithm

Problem Name: 1175. Prime Arrangements

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

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

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

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
```

Constraints:

• `1 <= n <= 100`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function isPrime(n) {
// Corner case
if (n <= 1) return false
// Check from 2 to n-1
for (let i = 2; i  <  n; i++) if (n % i == 0) return false
return true
}

const numPrimeArrangements = function(n) {
let primes = 0 // # of primes.
let result = 1
const mod = 10 ** 9 + 7
for (let i = 2; i  < = n; i++) if (isPrime(i)) primes++
// Calculate factorials and multiply.
for (let i = primes; i >= 1; i--) result = (i * result) % mod
for (let i = n - primes; i >= 1; i--) result = (i * result) % mod
return result // result of multiplying factorial(primes) with factorial(non-primes)
}
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
12

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numPrimeArrangements(self, n: int) -> int:
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
cnt = bisect.bisect(primes, n)
return math.factorial(cnt) * math.factorial(n - cnt) % (10 ** 9 + 7)
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
12

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Linq;

namespace LeetCode
{
public class _1175_PrimeArrangements
{
private readonly int MOD = 1000000007;

public int NumPrimeArrangements(int n)
{
var primes = new bool[n + 1];
for (int i = 2; i  < = n; i++)
primes[i] = true;

for (int i = 2; i * i  < = n; i++)
if (primes[i])
for (int j = i * i; j  < = n; j += i)
primes[j] = false;

var primeCount = primes.Count(p => p);

long result = 1;
for (int i = 2; i  < = primeCount; i++)
result = (result * i) % MOD;
for (int i = 2; i  < = n - primeCount; i++)
result = (result * i) % MOD;

return (int)result;
}
}
}
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
12