Easy to understand C# Solution with comments
\tpublic int CountPrimes(int n)\n        {\n            // using Sieve Of Eratosthenes\n\n            int counter = 0;\n            bool[] primes = new bool[n+1
\tpublic int CountPrimes(int n)\n        {\n            // using Sieve Of Eratosthenes\n\n            int counter = 0;\n            bool[] primes = new bool[n+1];\n\n            primes = Enumerable.Repeat(true, n+1).ToArray();\n        \n            for (int i = 2; i * i <= primes.Length; i++)\n            {\n                for (int j = i * i; j <= n; j+= i)\n                {\n                    primes[j] = false;\n                }\n            }\n\n            for (int i = 2; i < primes.Length; i++)\n            {\n                if (primes[i])\n                    counter++;\n            }\n  \n            return counter;\n        }\n\n        readonly int MOD = (int)Math.Pow(10, 9) + 7;\n\n        public int NumPrimeArrangements(int n)\n        { \n            int noOfprimes = CountPrimes(n);\n            decimal factorialPrimes = Factorial(noOfprimes);\n            decimal factoralNoPrimes = Factorial(n - noOfprimes);\n\n            // prime numbers are allowed to only shuffle in the prime positions\n\n\n            // Non - prime numbers are allowed to only shuffle in the non-prime positions\n\n\n            decimal product = (factorialPrimes * factoralNoPrimes) % MOD;\n\n            return (int)product;\n        }\n\n        public decimal Factorial(int n)\n        {\n            if (n <= 1) return 1;\n            return n * Factorial(n - 1) % MOD;\n        }
[]