c++ solution by counting the prime numbers
Intuition\n1. Given a number n, it is not very hard to calculate all the primes less than n and therefore, it is also easy to find out the power of a prime numb
# Intuition\n1. Given a number n, it is not very hard to calculate all the primes less than n and therefore, it is also easy to find out the power of a prime number for n!\n2. To calculate n!/k!, it is equal to caculate the difference of the power of prime numbers of n! and k!. \n\n# Approach\n1. For any given word, calculate its length n and all the duplicate characters c1, c2,...ck. Save n and c1, c2, ..ck into two different vectors\n2. For each word length n, and for each prime number p less than n, calculate the power of p in n!. Sum up the power of p for all the word length.\n3. Similarily, for a given duplicate c, calcualte the power of p in c! and reduce this power from the step 2.\n4. For all the prime numbers and corresponding power, calculate the answer with module of 1e9 + 7.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int countAnagrams(string s) {\n        long long ans = 1;\n        vector<int> wLens;\n        int nMaxLen = 0;\n        vector<int> dupLens;\n        for (int i = 0, idx = 0; i < s.size(); i = idx + 1)\n        {\n            idx = i;\n            vector<int> cm(26, 0);\n            for (; idx < s.size() && s[idx] != \' \'; idx++)     cm[s[idx] - \'a\']++;  \n            wLens.push_back(idx - i);\n            nMaxLen = max(nMaxLen, idx - i);\n            for (int j = 0; j < 26; ++j)\n                if (cm[j] > 1)  dupLens.push_back(cm[j]);\n        }\n\n        map<int, int> m;\n        vector<int> primes;\n        generatePrimes(nMaxLen + 1, primes);\n        for(int i = 0; i < wLens.size(); ++i)   addPrimeFactors(wLens[i], m, 1, primes);\n        for(int i = 0; i < dupLens.size(); ++i) addPrimeFactors(dupLens[i], m, -1, primes);\n        for (auto itr = m.begin(); itr != m.end(); ++itr)\n        {\n            for(int i = 0; i < itr->second; ++i)\n            {\n                ans = (ans * itr->first) % 1000000007;\n            }\n        }\n\n        return ans;\n    }\n\n    void addPrimeFactors(int n, map<int, int>& m, int w, vector<int>& primes)\n    {\n        vector<int> nums(n + 1, 0);\n        for(int i = 0; i < primes.size() && primes[i] <= n; ++i)\n        {\n            int count = 0;\n            for(long long num = primes[i]; num <= n; num = num * primes[i])   count += (n / num);\n            m[primes[i]] = m[primes[i]] + w*count;\n        }\n    }\n\n    void generatePrimes(int n, vector<int>& primes)\n    {\n        if (n <= 2)  return;\n        primes = {2};\n        vector<int> nums(n, 0);\n        for(int i = 3; i < n; i = i + 2)\n        {\n            if (nums[i] == 1)   continue;\n            primes.push_back(i);\n            for(int m = 3*i; m < n; m += 2*i)   nums[m] = 1;\n        }\n    }\n};\n```
['C++']