Nhảy không gian

Năm 2045, những con tàu thám hiểm có thể thực hiện các bước nhảy không gian tức thời, miễn là quãng đường nhảy không quá nguy hiểm.

Bản đồ là một lưới chữ nhật \(N\) hàng, \(M\) cột. Hàng được đánh số từ \(1\) đến \(N\) (từ trên xuống), cột từ \(1\) đến \(M\) (từ trái sang). Ô \((i, j)\) chứa 0 nếu là vùng an toàn, chứa 1 nếu là vùng không an toàn.

Con tàu xuất phát tại ô \((1, 1)\) và muốn tới ô \((N, M)\). Mỗi bước nhảy đi từ ô \((x, y)\) tới ô \((u, v)\) phải theo một trong hai hướng: xuống dưới (\(u > x\), \(v = y\)) hoặc sang phải (\(u = x\), \(v > y\)). Bước nhảy hợp lệ khi số ô không an toàn nằm trên đoạn đường từ \((x, y)\) đến \((u, v)\) (tính cả hai đầu mút \((x, y)\) và \((u, v)\)) không vượt quá \(D\).

Hãy đếm số cách đi khác nhau từ \((1, 1)\) tới \((N, M)\); hai cách đi là khác nhau nếu tập các ô mà tàu hạ cánh (điểm dừng sau mỗi bước nhảy, kể cả ô xuất phát và ô đích) khác nhau. Nói cách khác, mỗi cách đi là một dãy các ô \((1,1) = c_0, c_1, \dots, c_k = (N, M)\) với mọi bước nhảy \(c_{t} \to c_{t+1}\) hợp lệ. In ra kết quả theo modulo \(10^9 + 7\).

Input

• Dòng đầu chứa ba số nguyên \(N\), \(M\), \(D\).
• \(N\) dòng tiếp theo, mỗi dòng là một xâu gồm \(M\) ký tự 0 hoặc 1 mô tả bản đồ.

Output

In ra một số nguyên là số cách đi khác nhau, lấy phần dư khi chia cho \(10^9 + 7\).

Constraints

• \(2 \le N \times M \le 10^6\)
• \(0 \le D \le 10^9\)

Sample Input 1

2 3 1
010
100

Sample Output 1

5

Explanation

Năm cách đi (viết theo các ô hạ cánh):

• \((1,1) \to (1,3) \to (2,3)\)
• \((1,1) \to (1,2) \to (1,3) \to (2,3)\)
• \((1,1) \to (1,2) \to (2,2) \to (2,3)\)
• \((1,1) \to (2,1) \to (2,2) \to (2,3)\)
• \((1,1) \to (2,1) \to (2,3)\)

Bước nhảy \((1,1) \to (1,3)\) đi qua các ô \(0, 1, 0\) nên có đúng \(1\) ô không an toàn, thỏa \(D = 1\).