Коров'ячий Хоппскотч (Бронза)#11178
Так само, як людям подобається грати в гру Хоппскотч, корови Фермера Джона винайшли власну версію цієї гри. Гра «Коров'ячий Хоппскотч», у яку грають незграбні тварини вагою майже тонну, майже завжди закінчується катастрофою. Однак, дивно, але це не відлякало корів від гри майже кожного дня.
Гра відбувається на сітці розміром на , де кожна клітинка забарвлена або в червоний, або в синій колір. Корови починають у верхній лівій клітинці і повинні дістатися до нижньої правої клітинки, здійснюючи послідовність стрибків. Стрибок є допустимим тоді і лише тоді, коли:
Клітинка призначення має інший колір, ніж поточна клітинка.
Клітинка призначення знаходиться принаймні на один рядок нижче поточної клітинки.
Клітинка призначення знаходиться принаймні на один стовпець правіше поточної клітинки.
Допоможіть коровам визначити кількість різних послідовностей допустимих стрибків, які приведуть їх з верхньої лівої клітинки до нижньої правої клітинки.
У першому рядку містяться два цілих числа та c~(2 \le r \le 15, 2 \le c \le 15). Наступні рядків містять по символів кожен. Кожен символ є або '', або '', що позначає червону або синю клітинку відповідно.
Виведіть кількість різних способів дістатися з верхньої лівої клітинки до нижньої правої клітинки.
Приклад 1