Fugida del tauler P18760

Considereu un tauler d’escacs $n \times m$. Inicialment us trobeu a la cantonada de baix a la dreta, és a dir, a la posició $(n - 1, m - 1)$. El vostre objectiu és sortir del tauler. Hi ha algunes posicions prohibides, marcades amb asteriscos. Les caselles permeses tenen una ‘R’ o una ‘C’. Quan us trobeu sobre una ‘R’, podeu fer un moviment d’un rei dels escacs. Quan us trobeu sobre una ‘C’, podeu fer un moviment d’un cavall. A més, no podeu fer mai cap moviment que incrementi la fila o la columna on us trobeu. De quantes maneres diferents podeu sortir del tauler?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb dos naturals $n$ i $m$, ambdós entre 1 i 12. Segueixen $n$ línies amb $m$ caràcters cadascuna, els quals poden ser un asterisc, una ‘R’ o una ‘C’. La cantonada de baix a la dreta no té mai un asterisc.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents de sortir del tauler. Aquest nombre sempre és més petit que $10^9$.