Primul 11

În urma recentei victorii spectaculoase cu 3-0 a echipei naționale de fotbal a României împotriva Ucrainei, antrenorul Fisu' lu' Tasu' a început deja pregătirile pentru următorul meci cu Belgia. Cum partida se apropie și antrenorul are o problemă legată de formarea echipei, acesta are nevoie de ajutorul vostru. Ca recompensă pentru rezolvarea acestei probleme, Fisu' lu' Tasu' vă promite 3 puncte în meciul cu Belgia.

Cerință

Fisu' lu' Tasu' are la dispoziție $N$ jucători pentru a alege primul 11 al echipei naționale a României. Pentru fiecare jucător se cunosc pozițiile pe care acesta poate evolua în teren, sub forma unui string binar de $11$ cifre. Un $1$ pe o anumită poziție în string indică faptul că jucătorul poate evolua pe acea poziție, iar un $0$ indică faptul că nu poate juca pe acea poziție. Jucătorii de câmp nu pot sta în poartă, iar portarii nu pot juca în teren (prima poziție din string este asociată portarului). Fisu' lu' Tasu' vă cere să calculați numărul de moduri în care acesta poate să își aleagă primul 11, modulo $10^9 + 7$.

Date de intrare

Pe prima linie a fișierului de intrare primul-11.in se găsește un număr natural, $N$.
Pe următoarele $N$ linii se găsesc $N$ string-uri binare de 11 cifre, al $i$-lea string reprezentând pozițiile în care poate evolua jucătorul $i$.

Date de ieșire

Pe singura linie a fișierului de ieșire primul-11.out se va găsi un singur număr natural reprezentând numărul de moduri în care Fisu' lu' Tasu' poate să își aleagă primul 11, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• O echipă de fotbal (primul 11) este formată dintr-un portar și 10 jucători de câmp.
• Prima poziție din string-urile jucătorilor este asociată portarului.
• Într-un mod valid de a alege primul 11, există un jucător pe fiecare poziție din teren.
• Două echipe sunt diferite dacă există o poziție din cele 11 în care jucătorii din cele două echipe sunt diferiți.

Exemplu

primul-11.in

12
10000000000
10000000000
00001100000
00001010000
00000110000
01000000000
00110000000
00010001000
00000001000
00000000010
00000000100
00000000001

primul-11.out

4

Explicație

Sunt 4 moduri de a alege primul 11. După id-urile jucătorilor, acestea pot fi:

• $1$, $6$, $7$, $8$, $3$, $5$, $4$, $9$, $11$, $10$, $12$;
• $1$, $6$, $7$, $8$, $4$, $3$, $5$, $9$, $11$, $10$, $12$;
• $2$, $6$, $7$, $8$, $3$, $5$, $4$, $9$, $11$, $10$, $12$;
• $2$, $6$, $7$, $8$, $4$, $3$, $5$, $9$, $11$, $10$, $12$.

Al $i$-lea număr din echipele de mai sus reprezintă id-ul jucătorului de pe poziția $i$.