Fugida del tauler P18760

Considereu un tauler d’escacs n × 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⁹.