Bit erase

You are given a bit string with n characters. In each step, you may erase two adjacent bits that are the same. How many ways there are to erase all bits?

For example, when the bit string is 100111, there are 5 ways:

• 1\underline{00}111 \rightarrow \underline{11}11 \rightarrow \underline{11} \rightarrow (empty)
• 1\underline{00}111 \rightarrow 1\underline{11}1 \rightarrow \underline{11} \rightarrow (empty)
• 1\underline{00}111 \rightarrow 11\underline{11} \rightarrow \underline{11} \rightarrow (empty)
• 100\underline{11}1 \rightarrow 1\underline{00}1 \rightarrow \underline{11} \rightarrow (empty)
• 1001\underline{11} \rightarrow 1\underline{00}1 \rightarrow \underline{11} \rightarrow (empty)

You may assume that 1 \le n \le 30.

In a file biterase.py, implement a function count that returns the number of ways to erase all bits.

def count(s):
    # TODO

if __name__ == "__main__":
    print(count("1100")) # 2
    print(count("1001")) # 1
    print(count("100111")) # 5
    print(count("11001")) # 0
    print(count("1100110011100111")) # 113925