Write count_arrangements(s: str) -> int: how many different strings can be made by reordering all the letters of s? Return the count mod 1_000_000_007.
s can be a million characters long, so don't build the permutations, and avoid computing huge exact factorials as Python big ints. Aim for about O(n) plus a few modular powers.
count_arrangements("aabac") # 20 (5! / (3! · 1! · 1!))
count_arrangements("abc") # 6
count_arrangements("zzzz") # 1
count_arrangements("x") # 1
Constraints: 1 ≤ len(s) ≤ 10^6, s contains only a–z.
Show hint
Start from n! orderings of the positions and ask how many of them produce the same string when a letter repeats. Since the answer is taken mod a prime, replace each division by multiplication with a modular inverse (Fermat's little theorem gives one).