Bessie đang cố đi bộ từ đồng cỏ yêu thích của mình về chuồng.

Đồng cỏ và trang trại nằm trên một lưới \(N \times N\) (\(2 \leq N \leq 50\)), với đồng cỏ của Bessie ở góc trên bên trái và chuồng ở góc dưới bên phải. Bessie muốn về nhà càng sớm càng tốt nên cô chỉ đi xuống dưới và sang phải. Ở một số vị trí có các kiện cỏ khô mà Bessie không thể đi xuyên qua; cô phải đi vòng qua chúng.

Hôm nay Bessie hơi mệt nên cô muốn đổi hướng đi không quá \(K\) lần (\(1 \leq K \leq 3\)).

Bessie có thể đi từ đồng cỏ yêu thích về chuồng theo bao nhiêu đường đi phân biệt? Hai đường đi được coi là phân biệt nếu có một ô vuông mà Bessie đi qua trong đường này nhưng không đi qua trong đường kia.

Dữ liệu vào

Mỗi dữ liệu vào chứa \(T\) bộ dữ liệu con, mỗi bộ mô tả một trang trại khác nhau và tất cả đều phải được trả lời đúng để vượt qua toàn bộ dữ liệu. Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 50\)). Sau đó là \(T\) bộ dữ liệu con.

Mỗi bộ dữ liệu con bắt đầu bằng một dòng chứa \(N\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(N\) ký tự. Mỗi ký tự là . nếu ô đó trống hoặc H nếu ô đó có một kiện cỏ khô. Đảm bảo rằng góc trên bên trái và góc dưới bên phải của trang trại không chứa kiện cỏ khô.

Dữ liệu ra

In ra \(T\) dòng, dòng thứ \(i\) chứa số đường đi phân biệt Bessie có thể chọn trong bộ dữ liệu con thứ \(i\).

Phân nhóm

• Dữ liệu 2: \(K = 1\).
• Dữ liệu 3–5: \(K = 2\).
• Dữ liệu 6–10: \(K = 3\).

Ví dụ

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

2
4
6
2
0
0
6

Nguồn

USACO 2021 December Contest, Bronze — Walking Home. Tác giả: Nick Wu.

https://usaco.org/index.php?page=viewproblem2&cpid=1157