Sinulle on annettu merkkijonoja, joista jokainen koostuu merkeistä a ja b. Monellako tavalla merkkijonot voidaan jakaa kahteen joukkoon $X$ ja $Y$ niin, että molemmissa joukoissa on yhtä paljon kumpaakin merkkiä?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: merkkijonojen lukumäärä.

Tämän jälkeen tulee $n$ riviä, joista jokaisella on yksi merkkijono.

Tuloste

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

Esimerkki 1

Syöte:

5
aba
ba
aab
bba
abbab

Tuloste:

4

Selitys: Mahdolliset jakotavat ovat:

• $X=\{\textrm{aba, ba, bba}\}, Y=\{\textrm{aab, abbab}\}$
• $X=\{\textrm{aab, abbab}\}, Y=\{\textrm{aba, ba, bba}\}$
• $X=\{\textrm{aba, abbab}\}, Y=\{\textrm{aab, ba, bba}\}$
• $X=\{\textrm{aab, ba, bba}\}, Y=\{\textrm{aba, abbab}\}$

Esimerkki 2

Syöte:

4
a
a
a
a

Tuloste:

6

Selitys: Jakotapa on aina muotoa $X=\{\textrm{a, a}\}, Y=\{\textrm{a, a}\}$. Voidaan valita $6$ tavalla, mitkä merkkijonot ovat joukossa $X$.

Osatehtävä 1 (15 pistettä)

• Merkkijonoissa on yhteensä korkeintaan $16$ merkkiä

Osatehtävä 2 (55 pistettä)

• Merkkijonoissa on yhteensä korkeintaan $100$ merkkiä

Osatehtävä 3 (30 pistettä)

• Merkkijonoissa on yhteensä korkeintaan $500$ merkkiä