anagrams.cpp

void update(int x, int* sieve, std::map<int, int>& freq, int inc)
{
    while (x > 1)
    {
        int factor = sieve[x];
        freq[factor] += inc;
        x /= factor;
    }
}

int Anagrams(std::string word) {
    // Don't wanna do inverse mod
    int sieve[36] = 
    {
         0,  0,  2,  3,  2,
         5,  2,  7,  2,  3,
         2, 11,  2, 13,  2,
         3,  2, 17,  2, 19,
         2,  3,  2, 23,  2,
         5,  2,  3,  2, 29,
         2, 31,  2,  3,  2,
         5
    };
    
    int counts[26];
    for (int i = 0; i < 26; ++i)
        counts[i] = 0;
    
    int total = word.size();
    for (int i = 0; i < word.size(); ++i)
        ++counts[word[i] - 'a'];
    
    std::map<int, int> freq;
    for (int i = 2; i <= total; ++i)
        update(i, &sieve[0], freq, 1);
    
    for (int i = 0; i < 26; ++i)
        for (int j = 2; j <= counts[i]; ++j)
            update(j, &sieve[0], freq, -1);
    
    long long ans = 1;
    std::map<int, int>::iterator it;
    for (it = freq.begin(); it != freq.end(); ++it)
    {
        for (int i = 0; i < it->second; ++i)
        {
            ans *= it->first;
            ans %= (1000000007);
        }
    }
    
    return (int) ans;
}