[C++](Beats 100%)Simple solution with comments
We count the total number of primes till n. These are the positions where only primes can be permuted. But we also need to permute the remaining items to get th
We count the total number of primes till n. These are the positions where only primes can be permuted. But we also need to permute the remaining items to get the final result.\n\nWe calculate factorial of all required, instead of calculating it twice.\n\nCode:\n```\nclass Solution {\n    #define MOD 1000000007\npublic:\n    int numPrimeArrangements(int n) {\n        int count  = countPrimes(n+1);\n        int res;\n        vector<long int> a(101, 0);\n        fact(max(count, n-count), a);\n\t\t//result is product of count! * remaining!\n        res = (a[count]*a[n-count])%MOD;\n        return res;\n    }\n    //Helper method to calculate factorials\n    void fact(int n, vector<long int> &a){\n        a[0] = 1;\n        for(int i = 1; i <= n; i++){\n            a[i] = (i*a[i-1])%MOD;\n        }    \n    }\n    //Find total prime numbers count < n\n    int countPrimes(int n) {\n        vector<bool> prime(n, true);\n        \n        for(int i = 2; i*i < n; i++){\n            if(!prime[i]) continue;\n            for(int j = i*i; j < n; j += i){\n                prime[j] = false;\n            }\n        }\n        \n        int count = 0;\n        for(int i = 2; i < n; i++){\n            if(prime[i]) count++;\n        }\n        return count;\n    }\n};\n```
['C']