Explanation

This strategy is known as The Multinomial Theorem.

We are essentially counting how many distinct strings we can make by permuting the letters of the string. Note that if there are repeating characters in the string, permuting those characters in place counts as the same string since letters are indisguinshable.

For example, consider the string $aab$, and supposed we denote the $a$'s that appear in the string in order of which they appear, so the original string becomes $a_1a_2b$. One possible permutation is $a_2a_1b$. When we remove these subscripts, these two strings become the same thing.

To account for this, we'll go through each letter which occurs in the string and divide off the number of arrangements among its occurrences. The total number of permutations is $n!$. The number of ways a letter can permute is also just the factorial of the number of times it appears in the string.

Implementation

Time Complexity: $\mathcal{O}(MAXN * \log(MOD) + n)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int MAXN = 1e6;

array<ll, MAXN + 1> fact;  // fact[i] = i! % MOD
array<ll, MAXN + 1> inv;   // inv[i] = modular inverse of fact[i];

// calculate a ^ b (mod m) in log b time

Copy
from collections import Counter

MAXN = 10**6
MOD = 10**9 + 7

fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)


 Code Snippet: Combinatorics Functions (from the module) (Click to expand)