Bước nhảy không gian

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

Đọc từ tệp văn bản JUMP.INP có cấu trúc như sau:

• 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 tệp văn bản JUMP.OUT theo cấu trúc:

• Dòng \(1\): Ghi số nguyên \(t\) là kết quả của bài toán.

Example

2 3 1
101
010

4

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm: \(1 \le N \times M \le 5 \times 10^3\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm: \(D = 0\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm: không có ràng buộc gì thêm.