2025-08-02 11:54:02 +0000 UTC

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        prime = [True] * (n + 1)
        prime[0] = prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not prime[i]:
                continue
            for j in range(i * i, n + 1, i):
                prime[j] = False
                    
        prime_count = sum(prime)
        mod = 10**9 + 7
        fact_primes = math.factorial(prime_count)
        fact_norm = math.factorial(n - prime_count)
        return (fact_primes * fact_norm) % mod