C++: Faster 100% with explanation
Algorithm is simple (Upvotes are appreciated):\n1. Calculate how many numbers [1..n] are prime numbers\nSince indexes are counted from 1 then all prime numbers 
Algorithm is simple (**Upvotes are appreciated**):\n1. Calculate how many numbers `[1..n]` are prime numbers\nSince indexes are counted from `1` then all prime numbers are initially on their prime indexes.\nMeaning, number of prime numbers == number of prime indexes.\n2. Calculate how many not prime numbers: `n - count_of_prime_numbers`.\n3. Result would be: `permutations_of_all_prime_numbers_on_their_positions * permutations_of_all_not_prime_numbers_on_their_positions`.\n\nFormula for permutations count is simple, it\'s Factorial.\nSo if **a** is count of all prime numbers and **b** count of other numbers, then the result is:\n```\nreturn factorial(a) * factorial(b) % mod;\n// by init conditions mod == 10^9 + 7  == 1000000007\n```\n\nThe problem with the task is that max factorial we need to count is `75!` and it\'s waaaaay bigger than `ULONG_MAX`. **What to do?**\n\nRemember that `(a * b) mod c` is the same as `((a mod c) * (b mod c)) mod c` ? (check out [Properties of Modular Arithmetics](https://en.wikipedia.org/wiki/Modular_arithmetic#Properties))\n\nWe can use this rule to calculate Factorial: if value becomes bigger than `1000000007` we get the rest of devision on `1000000007`.\n\nThat\'s it!\n\nBut if we want to **achieve 0ms runtime** than we need to think that we calculate Factorial for **2 numbers** and most likely **one number is less than another**.\nWe can calculate **Factorial for smaller number** and then calculate Factorial for **second one**, but starting with **already calculated previous** value and not from `1` again.\n\n**Check out my code:**\n\n```\nclass Solution {\n    const long mod = 1000000007;\n    long factorial(int n, int prime = 2, long start = 1) {\n        long a = start;\n        for (int i = prime; i <= n; i++) {\n            a *= i;\n            if (a >= mod) a %= mod;\n        }\n        return a;\n    }\npublic:\n    int numPrimeArrangements(int n) {\n        int primes[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};\n        int i = 0;\n        for (; i < 25 && primes[i] <= n; i++);\n        int minNum = i, rest = n - i;\n        if (n < (i << 1)) swap(minNum, rest);\n        \n        long a = factorial(minNum), b = factorial(rest, minNum + 1, a);\n        return (int)(a * b % mod);\n    }\n};\n```
['C']