Omplint amb rajoles P73138

Donat un tauler $n \times m$ amb $c$ caselles ja marcades, cal acabar d’omplir-lo amb rajoles $1 \times 2$, cadascuna de les quals es pot posar horitzontalment o verticalment.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, $m$ i $c$, seguits de $c$ parells diferents $(x, y)$ indicant les caselles inicialment plenes. Podeu suposar que $n \cdot m$ està entre 2 i 45, que el nombre de caselles inicialment buides és parell, i que les files i columnes es numeren a partir de zero.

Sortida

Per a cada cas, escriviu el nombre de maneres d’acabar d’omplir la matriu.