Python solution using sieve of Erastosthenes
The key is to compute the value (n - p)! p!, where p is the number of primes between 1 and n (inclusive). To see this, if the p primes are to be fixed among "pr
The key is to compute the value **(n - p)! p!**, where *p* is the number of primes between 1 and *n* (inclusive). To see this, if the *p* primes are to be fixed among "prime locations" on the number line, there are *(n - p)!* ways to freely arrange the remaining (non-prime) integers. Since there are also *p!* ways to arrange the *p* primes themselves, we get *(n - p)! p!*.\n\n```\nclass Solution:\n    def numPrimeArrangements(self, n: int) -> int:\n        # Compute (with reduction by modulo 10^9 + 7 along the way)\n        # (n - noPrimes)! * noPrimes!\n        \n        MODULUS = 10**9 + 7\n        noPrimes = len (list(filter(lambda m : m, self.sieve(n))))\n        return self.pfact (n - noPrimes, MODULUS) * self.pfact(noPrimes, MODULUS) % MODULUS\n    \n    def sieve(self, n):\n        primes = [True] * (n+1)\n        primes[0] = primes[1] = False # 1 is not prime\n        \n        for i in range(2,n+1):\n            if primes[i]:\n                # "remove" multiples of the prime by marking them False\n                for j in range(2*i, n+1, i):\n                    primes[j] = False\n                    \n        return primes\n    \n    def pfact(self, n, p = 10^9 + 7):\n        if n == 0 or n == 1: return 1\n        \n        fact = 1\n        for i in range(2, n+1):\n            fact = fact * i % p\n            \n        return fact\n```
[]