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 \(\Rightarrow\), 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 \(\rightarrow\)). 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\).

Yêu cầu: 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.

Input

• Dòng đầu tiên ghi ba số nguyên dương \(m, n, k\) \((m, n \leq 30, k \leq 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 ).

Output

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(m, n \leq 5\).
• Subtask \(2\) (\(25\%\) số điểm): \(k = 1\).
• Subtask \(3\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 1
())
)()
)))

4