Giả sử đến năm ~2045~, giữa những vùng không gian vũ trụ, công nghệ dịch chuyển tức thời đã đạt đến một tầm cao mới. Những con tàu thám hiểm giờ đây có thể thực hiện những bước nhảy không gian chỉ trong nháy mắt, miễn là tuyến đường chúng chọn không quá nguy hiểm.

Bạn được giao nhiệm vụ điều khiển một con tàu thám hiểm di chuyển trong không gian được biểu thị bởi một bản đồ dạng lưới hình chữ nhật có kích thước ~N \times M~. Các hàng được đánh số thứ tự từ ~1~ đến ~N~, các cột được đánh số thứ tự từ ~1~ đến ~M~.

Ô ~(i, j)~ là ô ở hàng thứ ~i~ ~(1 \le i \le N)~ từ trên xuống dưới và cột thứ ~j~ ~(1 \le j \le M)~ từ trái sang phải trên bản đồ. Mỗi ô ~(i, j)~ biểu thị một vùng không gian, trong đó:

• Chứa giá trị ~0~ thì đó là vùng an toàn.
• Chứa giá trị ~1~ thì đó là vùng không an toàn. Tàu thám hiểm của bạn bắt đầu xuất phát tại ô ~(1, 1)~ và cần di chuyển đến đích là ô ~(N, M)~. Cơ chế di chuyển của con tàu tuân theo ~2~ quy định như sau:
• Hướng di chuyển hợp lệ: Từ vị trí ở ô ~(x, y)~ hiện tại, con tàu có thể thực hiện một bước nhảy đến vị trí mới ở ô ~(u, v)~ theo hai hướng: hướng xuống dưới ~(u > x, v = y)~ hoặc hướng sang phải ~(u = x, v > y)~.
• Bước nhảy hợp lệ: Trong một bước nhảy của con tàu từ ô ~(x, y)~ đến ô ~(u, v)~ thì tổng số vùng không an toàn nằm trên đường đi (bao gồm cả ô ~(x, y)~) không vượt quá giới hạn ~D~, lúc này bước nhảy là hợp lệ. Nếu vượt quá giới hạn này thì con tàu sẽ bị xé vụn.

Yêu cầu: Hãy đếm số cách khác nhau để tàu có thể di chuyển từ ô ~(1, 1)~ đến ô ~(N, M)~ theo cơ chế trên. Hai cách đi được xem là khác nhau nếu như có ít nhất một ô xuất hiện ở cách đi này nhưng không xuất hiện ở cách đi kia. Vì kết quả có thể rất lớn, hãy lấy phần dư của nó khi chia cho ~10^9 + 7~.

Input

Vào từ file văn bản JUMP.INP:

• Dòng 1: Chứa ba số nguyên ~N, M, D~ ~(1 \le N \times M \le 10^6, D \ge 0)~, tương ứng lần lượt là số hàng, số cột của bản đồ và giới hạn ~D~; các giá trị được ghi cách nhau một dấu cách.
• ~N~ dòng tiếp theo: mỗi dòng chứa một xâu gồm ~M~ kí tự '~0~' hoặc '~1~' mô tả bản đồ lưới.

Output

Ghi ra file văn bản JUMP.OUT: Một dòng ghi số nguyên ~t~ là kết quả bài toán.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N, M \leq 5 \times 10^3~;
• Subtask ~2~ ~(30\%)~: ~D = 0~;
• Subtask ~3~ ~(30\%)~: Không còn ràng buộc gì thêm.

Example input 1

2 3 1
101
010

Example output 1

4

Note 1

Các cách di chuyển từ ô (1,1) đến ô (2,3):

• Cách ~1~: ~(1,1) \to (2,1) \to (2,2) \to (2,3)~.
• Cách ~2~: ~(1,1) \to (2,1) \to (2,3)~.
• Cách ~3~: ~(1,1) \to (1,2) \to (2,2) \to (2,3)~.
• Cách ~4~: ~(1,1) \to (1,2) \to (1,3) \to (2,3)~.