Коров'ячі класики (Бронза)
Фермер Джон придумав гру для своїх корів.
Гра відбувається на решітці розміром r * c (2 ≤ r ≤ 15, 2 ≤ c ≤ 15), де кожна клітинка зафарбована в червоний або синій колір. Корови починають у лівому верхньому куті і повинні дістатися до правого нижнього кута, виконуючи послідовні стрибки. Стрибок вважається правильним, якщо і тільки якщо:
Ви стрибаєте на клітинку іншого кольору;
Клітинка, на яку Ви стрибаєте, знаходиться принаймні на один рядок нижче тієї, в якій Ви зараз перебуваєте;
Клітинка, на яку Ви стрибаєте, знаходиться принаймні на одну колонку правіше тієї, в якій Ви зараз перебуваєте.
Будь ласка, допоможіть коровам підрахувати кількість можливих різних послідовностей правильних стрибків з лівого верхнього кута до правого нижнього.
Вхідні дані
Перша строка містить два цілих числа r і c. Кожен з наступних r рядків містить рівно c символів. Кожен символ або R або B (позначають відповідно червоний або синій квадрат).
Вихідні дані
Виведіть кількість різних способів прострибати з лівого верхнього кута в правий нижній.