Comme les humains aiment la marelle, les vaches de Farmer John en ont inventé une variante. Jouée par des animaux maladroits de près d'une tonne, elle finit presque toujours en désastre, mais cela ne les empêche étonnamment pas d'essayer presque chaque après-midi.

Le jeu utilise une grille de $R$ lignes et $C$ colonnes ($2 \leq R \leq 15$, $2 \leq C \leq 15$), chaque case étant rouge ou bleue. Les vaches vont du coin supérieur gauche au coin inférieur droit par des sauts. Un saut est valide si et seulement si :

1. La case d'arrivée est d'une couleur différente ;
2. Elle est au moins une ligne plus bas que la case actuelle ; et
3. Elle est au moins une colonne plus à droite que la case actuelle.

Comptez les différentes suites de sauts valides allant du coin supérieur gauche au coin inférieur droit.

Entrée

La première ligne contient $R$ et $C$. Les $R$ suivantes contiennent chacune $C$ caractères. Chaque caractère est R ou B, pour une case rouge ou bleue respectivement.

Sortie

Affichez le nombre de façons différentes d'atteindre le coin inférieur droit depuis le coin supérieur gauche par des sauts.

Exemples

Entrée 1

4 4
RRRR
RRBR
RBBR
RRRR

Sortie 1

3

Auteur du problème : Nick Wu, 2015