karma

Karma

== include(page="template/taskheader" task_id="karma") ==

Poveste şi cerinţă...
 
Se dau N siruri de paranteze de dimensiune M. Putem vedea aceste siruri ca o matrice de N * M.
 
In cate moduri putem permuta coloanele matricei astfel incat fiecare linie sa devina o parantezare corecta?
 
N <= 20
M <= 20

Se da o matrice cu $N$ linii si $M$ coloane cu paranteze deschise si inchise (avem doar elemente de tipul "(" si ")"). In cate moduri se pot permuta coloanele matricei astfel incat fiecare linie sa devina o parantezare corecta?

h2. Date de intrare

Fişierul de intrare $karma.in$ ...

Fişierul de intrare $karma.in$ va contine pe prima linie $N$ si $M$. Pe urmatoarele $N$ linii se afla cate un sir de $M$ paranteze.

h2. Date de ieşire

În fişierul de ieşire $karma.out$ ...

Fişierul de ieşire $karma.out$ va contine un singur numar reprezentand raspunsul *$modulo 1.000.000.007$*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 20$

h2. Exemplu
table(example). |_. karma.in |_. karma.out |

|2 4
(())
()()
|2
|

|3 8
(((())))
()()(())
))((()()

|168???

|168

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="karma") ==