Giống như con người thích chơi nhảy lò cò, những con bò của Nông dân John đã sáng tạo ra một biến thể của trò chơi này dành riêng cho mình. Vì người chơi là những con vật vụng về nặng gần một tấn, trò nhảy lò cò của bò hầu như luôn kết thúc trong thảm họa, nhưng đáng ngạc nhiên là điều đó vẫn không ngăn đàn bò cố gắng chơi trò này gần như mỗi buổi chiều.

Trò chơi diễn ra trên một lưới \(R \times C\) (\(2 \leq R \leq 15\), \(2 \leq C \leq 15\)), trong đó mỗi ô được tô màu đỏ hoặc xanh dương. Những con bò bắt đầu ở ô trên cùng bên trái và di chuyển đến ô dưới cùng bên phải bằng một dãy các bước nhảy. Một bước nhảy hợp lệ khi và chỉ khi:

1. Ô đích có màu khác với ô hiện tại.

2. Ô đích nằm dưới ô hiện tại ít nhất một hàng.

3. Ô đích nằm bên phải ô hiện tại ít nhất một cột.

Hãy giúp đàn bò tính số dãy bước nhảy hợp lệ khác nhau có thể đưa chúng từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Dữ liệu vào

Tệp hopscotch.in:

Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\). Mỗi dòng trong \(R\) dòng tiếp theo chứa \(C\) ký tự. Mỗi ký tự là R hoặc B, lần lượt biểu thị một ô màu đỏ hoặc màu xanh dương.

Dữ liệu ra

Tệp hopscotch.out:

In số cách khác nhau để nhảy từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Ví dụ

4 4
RRRR
RRBR
RBBR
RRRR

3

Nguồn

USACO 2015 February Contest, Bronze — Cow Hopscotch (Bronze)

Tác giả bài: Nick Wu, 2015.