Omplint amb rajoles P73138

Donat un tauler n × m amb c caselles ja marcades, cal acabar d’omplir-lo amb rajoles 1 × 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 · 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.