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ä