Mê cung ngoặc

Một mê cung được mô tả bằng bảng chữ hình chữ nhật kích thước $m\times n$. Các hàng của bảng được đánh số từ $1$ đến $m$, từ trên xuống dưới, các cột của bảng được đánh số từ $1$ đến $n$, từ trái qua phải. Ô nằm trên giao của hàng $i$ và cột $j$ được gọi là ô $(i,j)$. Mỗi ô của lưới chứa một kí tự ngoặc mở ( hoặc ngoặc đóng ).

Người chơi sẽ xuất phát từ ô $(1,1)$, quay hướng tới phía ô $(1,n)$ và di chuyển trên bảng. Việc di chuyển phải tuân thủ các quy tắc được mô tả trong hình trên, cụ thể: từ ô đang đứng, căn cứ vào hướng đang hướng tới được chỉ ra bởi mũi tên $\to$, thực hiện bước di chuyển sang ô kề cạnh đang hướng tới, hoặc sang ô kề cạnh nằm bên phải (các hướng có thể di chuyển được chỉ ra bởi các mũi tên $\to$). Mỗi ô chỉ được đi qua nhiều nhất một lần. Người chơi có thể dừng di chuyển tại một ô nào đó để kết thúc trò chơi.

Khi kết thúc trò chơi, người chơi nhận được một xâu kí tự $T$ gồm các kí tự trong các ô trên đường đi được xếp liên tiếp nhau. Người chơi giành chiến thắng nếu xâu $T$ là một biểu thức ngoặc đúng bậc $k$.

Nhắc lại, định nghĩa biểu thức ngoặc đúng và bậc của biểu thức ngoặc:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng $0$,
• Nếu $A$ là biểu thức ngoặc đúng có bậc bằng $k$ thì $(A)$ cũng là một biểu thức ngoặc đúng có bậc bằng $k+1$,
• Nếu $A$ và $B$ là hai biểu thức ngoặc đúng và có bậc tương ứng là $k_1$ và $k_2$ thì $AB$ cũng là một biểu thức ngoặc đúng có bậc bằng $max(k_1,k_2)$.

Ví dụ, ()() là một biểu thức ngoặc đúng có bậc bằng $2$ còn (()()) là một biểu thức ngoặc đúng và có bậc bằng $3$.

Cho bảng chữ và số nguyên dương $k$, đếm số lượng đường đi khác nhau giúp người chơi giành chiến thắng. Hai đường đi được gọi là khác nhau nếu tồn tại một ô thuộc đường đi này nhưng không thuộc đường đi kia.

Dữ liệu vào

• Dòng đầu tiên ghi ba số nguyên dương $m,n,k$ ($m,n\le 30$; $k\le 10$);
• Tiếp theo là $m$ dòng mô tả bảng chữ, mỗi dòng chứa một xâu gồm $n$ kí tự, mỗi kí tự ngoặc mở ( hoặc ngoặc đóng ).

Dữ liệu ra

Một dòng là số lượng đường đi đếm được chia dư cho (${10}^9+7$).

Ràng buộc

• $m,n\le 30$; $k\le 10$
• Subtask 1 (50 điểm): $m,n\le 5$
• Subtask 2 (25 điểm): $k=1$
• Subtask 3 (25 điểm): Không có ràng buộc gì thêm.

Ví dụ