Moviments en el pla P77684

Teniu $n$ vectors bidimensionals $(x_i, y_i)$ i una posició objectiu $(x, y)$. Inicialment, us trobeu a $(0, 0)$. En ordre, heu de decidir com usar cada vector: podeu descartar-lo, sumar $x_i$ a la vostra $x$ actual, sumar $y_i$ a la vostra $y$ actual, o fer les dues coses. Heu d’anar fins a $(x, y)$ almenys un cop, i acabar a $(0, 0)$. De quantes maneres podeu fer-ho?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $x$, $y$ i $n$, seguides dels $n$ vectors $(x_i, y_i)$. Suposeu $2 \le n \le 12$, i que $x$, $y$, $x_i$ i $y_i$ són enters entre $-10^6$ i $10^6$ diferents de 0.

Sortida

Per a cada cas, escriviu el nombre de maneres d’anar fins a $(x, y)$ almenys una vegada i tornar a $(0, 0)$.

Observació

La solució esperada és un backtracking sense esporgar, però en la correcció manual valorarem positivament solucions més astutes.