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ả trên 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 $\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.

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 \le 30; k \le 10~);
• Tiếp theo là ~m~ dòng mô tả bảng chữ, mỗi dòng gồm đúng ~n~ kí tự, mỗi kí tự là ngoặc mở '(' hoặc ngoặc đóng ')'.

Output

Số lượng đường đi đếm được chia dư cho ~998244353~.

Sample Input 1

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

Sample Output 1

4

Subtasks

• 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.