public class Solution {
const int MOD = 1_000_000_007;
public int NumPrimeArrangements(int n)
{
var cnt = PrimeCount(n);
var f = Factorial(Math.Max(cnt, n - cnt));
return (int)(f[cnt] * f[n - cnt] % MOD);
}
int PrimeCount(int n)
{
var ba = new BitArray(n + 1);
var ret = 0;
for (var i = 2; i <= n; i++)
{
if (!ba[i])
{
ret++;
for (var j = 2 * i; j <= n; j += i)
ba[j] = true;
}
}
return ret;
}
long[] Factorial(int max)
{
var ret = new long[max + 1];
ret[0] = 1;
for (var i = 1; i < ret.Length; i++)
ret[i] = ret[i - 1] * i % MOD;
return ret;
}
}