You have a string of lowercase letters. One move deletes two adjacent equal letters; the pieces on either side then join up. You want to delete everything.
Write count_ways(s: str) -> int: the number of different move sequences that empty the string, modulo 10**9 + 7. Two sequences differ if at some step they delete a different pair.
Examples:
count_ways("aabb") == 2(deleteaathenbb, orbbthenaa)count_ways("abba") == 1(bbmust go first)count_ways("aaaa") == 3(first move: the left, middle or right pair; then one move left)count_ways("abc") == 0
Constraints: 1 <= len(s) <= 500. The tests use up to 240 characters, so simulating moves is hopeless; aim for O(n³).
Show hint
in s[l..r], the first letter s[l] is eventually deleted together with some s[k] where s[k] == s[l]. Everything strictly between them must vanish first, and the part after k is independent. The two independent groups of moves can be interleaved in any order; count interleavings with a binomial coefficient.