easy to understand || must see
Code\n\nclass Solution {\npublic:\n    const int mod = 1e9+7;\n    vector<bool>dp;\n    unordered_map<long long int,long long int>memo;\n    int numPrimeArrange
# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9+7;\n    vector<bool>dp;\n    unordered_map<long long int,long long int>memo;\n    int numPrimeArrangements(int n) \n    {\n         dp.resize(n+1,true);  //initally considering all to be prime\n         dp[0] = false;\n         dp[1] = false;\n\n         for(int i=2;i<dp.size();i++)\n         {\n             //if the curr num is prime\n             if(dp[i] == true)\n             {\n                 for(int j=i+i;j<dp.size();j+=i)\n                 {\n                     dp[j] = false;\n                 }\n             }\n         }\n        int composite = 0;\n        int prime = 0;\n        for(int i=1;i<dp.size();i++)\n        {\n            if(dp[i] == true) prime++;\n            else composite++;\n        }\n        //cout<<"prime = "<<prime<<endl;\n        //cout<<"composite = "<<composite<<endl;\n\n        int val1 = fact(prime)%mod;\n        //cout<<"val1 = "<<val1<<endl;\n\n        int val2 = fact(composite)%mod;\n        //cout<<"val2 = "<<val2<<endl;\n\n        int ans = (1LL * val1 * val2)%mod;\n        return ans;\n    }\n    int fact(int num)\n    {\n        if(num == 1)\n        return 1;\n\n        if(num == 0)\n        return 1;\n      \n        if(memo.find(num) != memo.end())\n        {\n            return memo[num];\n        }\n\n        return memo[num] = (1LL * num * fact(num-1))%mod;\n    }\n    \n};\n\n```
['Math', 'C++']