Bittipoisto

Annettuna on bittijono, jossa on n merkkiä. Joka askeleella saat poistaa kaksi vierekkäistä bittiä, jotka ovat eri bitit. Monellako tavalla voit poistaa kaikki bitit?

Esimerkiksi kun bittijono on 101100, mahdollisia tapoja on 5:

• \underline{10}1100 \rightarrow 1\underline{10}0 \rightarrow \underline{10} \rightarrow (tyhjä)
• 1\underline{01}100 \rightarrow 1\underline{10}0 \rightarrow \underline{10} \rightarrow (tyhjä)
• 101\underline{10}0 \rightarrow \underline{10}10 \rightarrow \underline{10} \rightarrow (tyhjä)
• 101\underline{10}0 \rightarrow 1\underline{01}0 \rightarrow \underline{10} \rightarrow (tyhjä)
• 101\underline{10}0 \rightarrow 10\underline{10} \rightarrow \underline{10} \rightarrow (tyhjä)

Voit olettaa, että 1 \le n \le 30. Koodisi tulee toimia tehokkaasti kaikissa näissä tapauksissa.

Toteuta tiedostoon biterase.py funktio count, joka kertoo, monellako tapaa voit poistaa kaikki bitit.

def count(s):
    # TODO

if __name__ == "__main__":
    print(count("1001")) # 2
    print(count("1100")) # 1
    print(count("101100")) # 5
    print(count("11001")) # 0
    print(count("01110100100110")) # 6027