Người ta kể rằng các ninja dùng mật mã khi gửi thông điệp cho đồng đội để ninja đối phương không đọc được. Có nhiều loại mật mã, trong đó một loại sử dụng tờ mã hóa đặc biệt.

Trên tờ mã hóa có một bảng ô vuông gồm \(M\) hàng và \(N\) cột. Mỗi ô trong số \(MN\) ô chứa một ký tự. Ô ở hàng thứ \(a\) từ trên xuống, cột thứ \(b\) từ trái sang được ký hiệu là \((a,b)\).

Một thông điệp được biểu diễn bởi một đường đi ngắn nhất từ ô trên cùng bên trái \((1,1)\) đến ô dưới cùng bên phải \((M,N)\). Đường đi ngắn nhất là một dãy ô thu được bằng cách chỉ đi sang ô kề bên phải hoặc ô kề bên dưới cho đến đích. Thông điệp của đường đi là xâu gồm \(M+N-1\) ký tự trong các ô được đi qua, ghép theo thứ tự trên đường đi.

Các ninja trong cùng nhóm thống nhất trước một đường đi ngắn nhất, rồi dùng những tờ mã hóa khác nhau để gửi thông điệp. Vì không biết đường đi đã chọn, ninja đối phương không thể đọc được thông điệp ngay cả khi lấy được tờ mã hóa.

Tuy nhiên, số đường đi ngắn nhất trên bảng có thể rất lớn, và những đường đi khác nhau có thể biểu diễn cùng một thông điệp. Với một số cách sắp xếp ký tự, có nhiều đường đi biểu diễn cùng một thông điệp, khiến đối phương dễ đọc được thông điệp hơn.

Độ mạnh của tờ mã hóa được đo theo quy trình sau:

1. Bắt đầu tại \((1,1)\). Ở mỗi bước, chọn đi sang phải hoặc xuống dưới với xác suất bằng nhau. Nếu đang ở hàng dưới cùng thì đi sang phải với xác suất \(1\); nếu đang ở cột ngoài cùng bên phải thì đi xuống với xác suất \(1\). Dừng khi đến \((M,N)\), thu được một đường đi ngắn nhất \(s\).
2. Gọi \(f(s)\) là số đường đi ngắn nhất trên bảng biểu diễn cùng thông điệp với \(s\). Tính cả chính đường đi \(s\), nên \(f(s)\ge1\).
3. Gọi \(E\) là kỳ vọng của \(f(s)\) theo cách chọn đường đi ở bước 1. Nói cách khác, với mỗi đường đi ngắn nhất \(t\), lấy \(f(t)\) nhân với xác suất chọn được \(t\), rồi cộng trên tất cả các đường đi \(t\). Giá trị \(E\) được dùng làm thước đo độ mạnh của tờ mã hóa.

Vì \(E\) có thể không phải số nguyên, ta cần tính \(E\times2^{M+N}\). Giá trị này có thể rất lớn, nên chỉ cần tìm số dư khi chia cho \(1\,000\,000\,007\).

Yêu cầu

Cho kích thước bảng và cách sắp xếp các ký tự, hãy tính

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(M,N\), phân cách bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa một xâu gồm đúng \(N\) chữ cái tiếng Anh in hoa. Ký tự thứ \(j\) của xâu này là ký tự trong ô \((i,j)\).

Dữ liệu ra

Ghi ra đầu ra chuẩn số dư khi \(E\times2^{M+N}\) chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1\le M\le300\).
• \(1\le N\le300\).
• Mỗi ô chứa một chữ cái tiếng Anh in hoa từ A đến Z.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\) và \(N\le10\).

Ví dụ

2 3
JOI
III

48

4 4
AAAA
AAAA
AAAA
AAAA

5120