pre-computation (sieve + prefix) + math (factorial) || optimal
\n# Approach\n Describe your approach to solving the problem. \nAs, precomputation\n1. Make sieve\n2. Apply prefix\n\nIn main function,\n1. Calculate factorial 
\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAs, precomputation\n1. Make sieve\n2. Apply prefix\n\nIn main function,\n1. Calculate factorial (considering Mod=1e9+7)\nfact(prefix[n])\nfact(prefixn-prefix)\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <iostream>\n#include <vector>\n\nconst long long MOD = 1e9 + 7;\n\nclass Solution {\nprivate:\n    std::vector<int> prefix;\n\npublic:\n    Solution() {\n        prefix.assign(101, 1);\n        prefix[0] = 0;\n        prefix[1] = 0;\n        for (int i = 2; i <= 100; i++) {\n            if (prefix[i]) {\n                for (int j = i * i; j <= 100; j += i) {\n                    prefix[j] = 0;\n                }\n            }\n        }\n        for (int i = 1; i <= 100; i++) {\n            prefix[i] += prefix[i - 1];\n        }\n    }\n    long long fact(int n){\n        long long result=1;\n        for(int i=1; i<=n; i++){\n            result*=i;\n            result%=MOD;\n        }\n        return result;\n    }\n    int numPrimeArrangements(int n) {\n        return (fact(prefix[n])*fact(n-prefix[n]))%MOD;\n    }\n};\n\n\n```
['Math', 'Prefix Sum', 'C++']