Có thể coi đồng cỏ của Farmer John là một lưới hai chiều rộng gồm các ô vuông, giống như một bàn cờ khổng lồ. Các ô được gán nhãn bằng cặp có thứ tự \((i,j)\) với mọi \(1\le i\le N\), \(1\le j\le N\) (\(1\le N\le150\)). Một số ô có cỏ.

Một tập con không rỗng của các ô lưới được gọi là “cân bằng” nếu thỏa mãn các điều kiện sau:

1. Mọi ô trong tập con đều có cỏ.
2. Tập con liên thông bốn hướng. Nói cách khác, giữa hai ô bất kỳ trong tập con luôn tồn tại một đường đi sao cho hai ô liên tiếp trên đường đi kề nhau theo chiều ngang hoặc dọc.
3. Nếu các ô \((x_1,y)\) và \((x_2,y)\), với \(x_1\le x_2\), thuộc tập con, thì mọi ô \((x,y)\) với \(x_1\le x\le x_2\) cũng thuộc tập con.
4. Nếu các ô \((x,y_1)\) và \((x,y_2)\), với \(y_1\le y_2\), thuộc tập con, thì mọi ô \((x,y)\) với \(y_1\le y\le y_2\) cũng thuộc tập con.

Hãy đếm số tập con cân bằng, lấy phần dư theo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(N\) ký tự. Ký tự thứ \(j\) của dòng thứ \(i\) tính từ trên xuống là G nếu ô \((i,j)\) có cỏ, và là . nếu không có cỏ.

Dữ liệu ra

In số tập con cân bằng lấy phần dư theo \(10^9+7\).

Phân nhóm

• Các test 1-4 thỏa mãn \(N\le4\).
• Các test 5-10 thỏa mãn \(N\le20\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

2
GG
GG

13

4
GGGG
GGGG
GG.G
GGGG

642

Giải thích ví dụ 1. Trong bộ test này, mọi tập con liên thông bốn hướng đều cân bằng:

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

Giải thích ví dụ 2. Dưới đây là một tập con thỏa mãn điều kiện thứ hai, tức liên thông bốn hướng, nhưng không thỏa mãn điều kiện thứ ba:

GG..
.G..
GG..
....

Nguồn

USACO 2021 US Open, Platinum - Balanced Subsets: https://usaco.org/index.php?page=viewproblem2&cpid=1142

Tác giả: Benjamin Qi.