Creating Strings II.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxN = 1e6+5;
const ll MOD = 1e9+7;

int N, freq[26];
char S[maxN];
ll fact[maxN], inv[maxN];

ll inverse(ll x){
    ll res = 1;
    ll expo = MOD-2;
    while(expo > 0){
        if(expo&1)
            res = (res * x) % MOD;
        x = (x * x) % MOD;
        expo >>= 1;
    }
    return res;
}

void init(){
    fact[0] = inv[0] = 1;
    for(int i = 1; i < maxN; i++){
        fact[i] = i * fact[i-1] % MOD;
        inv[i] = inverse(fact[i]);
    }
}

int main(){
    scanf("%s", S);
    N = (int) strlen(S);
    init();

    for(int i = 0; i < N; i++)
        freq[(int) (S[i]-'a')]++;

    ll ans = fact[N];
    for(int i = 0; i < 26; i++)
        ans = ans * inv[freq[i]] % MOD;
    printf("%lld\n", ans);
}