Wie Menschen Himmel und Hölle spielen, haben Farmer Johns Kühe eine eigene Variante erfunden. Bei ungeschickten Tieren mit fast einer Tonne Gewicht endet das Spiel fast immer katastrophal. Überraschenderweise versuchen sie dennoch fast jeden Nachmittag zu spielen.
Gespielt wird auf einem Gitter mit $R$ Zeilen und $C$ Spalten ($2 \leq R \leq 15$, $2 \leq C \leq 15$), dessen Felder rot oder blau sind. Die Kühe springen von oben links nach unten rechts. Ein Sprung ist genau dann gültig, wenn:
- Das Zielfeld eine andere Farbe hat;
- Es mindestens eine Zeile unter dem aktuellen Feld liegt; und
- Es mindestens eine Spalte rechts vom aktuellen Feld liegt.
Zähle die verschiedenen gültigen Sprungfolgen von oben links nach unten rechts.
Eingabe
Die erste Zeile enthält $R$ und $C$. Die nächsten $R$ Zeilen enthalten je $C$ Zeichen. Jedes ist R oder B und steht für ein rotes beziehungsweise blaues Feld.
Ausgabe
Gib die Anzahl verschiedener Wege aus, von oben links nach unten rechts zu springen.
Beispiele
Eingabe 1
4 4 RRRR RRBR RBBR RRRR
Ausgabe 1
3
Aufgabenautor: Nick Wu, 2015