Trong một vùng đất bị lãng quên, tồn tại một mê cung cổ đại hình chữ nhật được chia thành ~N~ hàng và ~M~ cột. Tương truyền, ở góc sâu nhất của mê cung - nơi bóng tối ngự trị - cất giấu một viên ngọc vàng mang sức mạnh vô hạn.

Thời gian trước, An tham gia thử thách "Khởi nguyên mê cung", cảm thấy rất thú vị và ý nghĩa. An đã học hỏi, trải nghiệm và nâng cao chuyên môn thành một nhà thám hiểm thực thụ. Lần này, An quyết tâm chinh phục mê cung và tìm viên ngọc hoàng kim quý giá. An đã bước vào mê cung từ ô xuất phát ~(1,1)~. Tuy nhiên, những quy luật kỳ lạ của mê cung chỉ cho phép An di chuyển theo quy luật:

• Chỉ có thể tiến sang phải hoặc đi xuống.

• Mỗi ô ~(i,j)~ đều ẩn chứa một con số bí ẩn mang nguồn năng lượng ~a[i,j]~. Mỗi bước đi qua, An sẽ hấp thụ giá trị đó và nâng cao sức mạnh.

Trên cổng mê cung có một câu sấm truyền: "Chỉ những con đường mà tổng năng lượng hấp thụ đúng bằng con số định mệnh ~K~ mới dẫn tới viên ngọc".

Liệu An có thể phá giải lời nguyền của mê cung, hay sẽ lạc lối mãi mãi trong những con số vô tận?

Nhiệm vụ

Với tư duy thuật toán siêu phàm và sự hỗ trợ của máy tính, bạn hãy lập trình khám phá xem có bao nhiêu con đường hợp lệ đi từ vị trí xuất phát ~(1,1)~ đến ~(N,M)~ sao cho tổng giá trị các ô trên đường đi chính xác bằng ~K~.

Do số lượng con đường có thể rất lớn, hãy trả về kết quả theo modul ~10^9 + 7~.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(1 \le N, M \le 80, 0 \le K \le 10^{18})~, lần lượt là số hàng, số cột của mê cung và tổng giá trị cần đạt.

• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên không âm ~A[i,j]~ ~(0 \le A[i,j] \le 10^9)~, là giá trị của các ô trong mê cung.

• Các số trên mỗi dòng cách nhau bởi một dấu cách.

Output

Một số nguyên duy nhất, là số lượng đường đi hợp lệ từ ~(1, 1)~ đến ~(N, M)~ có tổng giá trị bằng ~K~, lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

6 5 50
5 5 5 5 5
5 5 5 5 5
5 6 5 5 5
5 5 5 5 5
5 5 5 5 5
5 5 5 5 7

Sample Output 1

0

Sample Input 2

3 3 6
1 2 1
1 4 1
1 2 1

Sample Output 2

2