Annettuna on merkkijono, jossa on $n$ merkkiä väliltä a–z.

Saat poistaa merkkijonosta joka vuorolla kaksi vierekkäistä merkkiä, jotka ovat samat. Tavoitteesi on tyhjentää merkkijono poistamalla sen kaikki merkit.

Montako mahdollista tapaa on tyhjentää merkkijono?

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on $n$ merkkiä.

Tuloste

Tulosta yksi kokonaisluku: tapojen määrä modulo $10^9+7$.

Rajat

• $1 \le n \le 1000$

Esimerkki

Syöte:

aabccb

Tuloste:

3