A playlist is described by a string s; each character is the genre of one song, and songs of the same genre are interchangeable. The player shuffles the songs uniformly at random: all n! orders of the n songs are equally likely (equivalently, every distinct rearrangement of the string s is equally likely).
The shuffle is calm if no two adjacent songs have the same genre. Return the probability that the shuffle is calm, as an exact reduced fraction in the string form "p/q" with q >= 1 and gcd(p, q) = 1. Use "0/1" when a calm order is impossible and "1/1" when every order is calm.
Examples
Input: s = "aab"
Output: "1/3"
Explanation: of the rearrangements aab, aba, baa only aba is calm.
Input: s = "aabb"
Output: "1/3"
Explanation: abab and baba are calm, out of 6 rearrangements.
Constraints
1 <= len(s) <= 400sconsists of lowercase English letters- The numerator and denominator can have hundreds of digits. Floating-point values are not accepted, and listing the rearrangements is hopeless beyond a dozen songs.
Goals
- Count arrangements of a multiset with no two equal neighbours
- Use inclusion-exclusion over how each letter's copies are glued into blocks
- Report an exact probability as a reduced fraction of big integers