Java - 1 ms
\nclass Solution {\n    final int MOD = 1000000007;\n    \n    public int numPrimeArrangements(int n) {\n        int p = countPrimes(n);\n        \n        int 
```\nclass Solution {\n    final int MOD = 1000000007;\n    \n    public int numPrimeArrangements(int n) {\n        int p = countPrimes(n);\n        \n        int i;\n        long prod = 1;\n        \n        for(i = 1; i <= p; i++){\n            prod = (prod * i) % MOD;\n        }\n        \n        for(i = 1; i <= (n - p); i++){\n            prod = (prod * i) % MOD;     // number of desired permutations = p! * (n - p)!\n        }\n        \n        return (int)prod;\n    }\n    \n    private int countPrimes(int n){\n        if(n < 2)\n            return 0;\n        else{\n            boolean[] prime = new boolean[n + 1];\n            Arrays.fill(prime, true);\n            prime[0] = false;\n            prime[1] = false;\n            \n            int i, j, k, x, count = 0;\n            \n            for(i = 2; i <= n; i++){\n                k = n / i;\n                x = i;\n                for(j = 2; j <= k; j++){\n                    x = x + i;\n                    prime[x] = false;\n                }\n            }\n            \n            for(i = 2; i <= n; i++){\n                if(prime[i]){\n                    ++count;\n                }\n            }\n            \n            return count;\n        }\n    }\n}\n```
[]