Bessie đã trở thành một họa sĩ và đang sáng tác những bức tranh về hang động! Tác phẩm hiện tại của cô là một lưới cao \(N\) hàng, mỗi hàng có đúng \(M\) ô vuông (\(1\le N,M\le 1000\)). Mỗi ô vuông ở một trong ba trạng thái: trống, chứa đá hoặc chứa nước. Bessie đã tô những ô chứa đá, bao gồm toàn bộ đường biên của bức tranh. Giờ đây, cô muốn tô một số ô trống bằng nước sao cho nếu bức tranh là thật thì nước không có chuyển động ròng. Định nghĩa độ cao của một ô ở hàng thứ \(i\) tính từ trên xuống là \(N+1-i\). Bessie muốn bức tranh của mình thỏa mãn điều kiện sau:

Giả sử ô \(a\) chứa nước. Nếu tồn tại một đường đi từ \(a\) đến ô \(b\) chỉ qua các ô trống hoặc ô chứa nước có độ cao không lớn hơn ô \(a\), sao cho mỗi hai ô liên tiếp trên đường đi có chung một cạnh, thì ô \(b\) cũng phải chứa nước.

Hãy tìm số bức tranh khác nhau Bessie có thể tạo ra, lấy modulo \(10^9+7\). Bessie có thể tô bằng nước một số lượng ô trống bất kỳ, kể cả không tô ô nào hoặc tô tất cả các ô.

Phân nhóm

• Các test từ \(1\) đến \(5\) thỏa mãn \(N,M\le 10\).
• Các test từ \(6\) đến \(15\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp cave.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự. Mỗi ký tự là . hoặc #, lần lượt biểu thị một ô trống và một ô chứa đá. Hàng đầu tiên, hàng cuối cùng, cột đầu tiên và cột cuối cùng chỉ chứa ký tự #.

Dữ liệu ra

Ghi ra tệp cave.out một số nguyên: số bức tranh thỏa mãn điều kiện, lấy modulo \(10^9+7\).

Ví dụ

4 9
#########
#...#...#
#.#...#.#
#########

9

Nguồn

• Kỳ thi: USACO 2020 January Contest, Platinum
• Tên bài: Cave Paintings
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=996
• Tác giả đề: Daniel Zhang