Kinh đô của đế quốc ByteLand nằm bên bìa khu Rừng Thiêng, mà ở tận sâu bên trong Rừng Thiêng chính là hang ổ của bọn quái vật. Trong một lần đi dạo vào rừng cùng thị vệ, công chúa BlockyBlock đã bị quái vật bắt cóc mang về hang ổ. Để giải cứu cho con gái, quốc vương ban bố sẽ gả công chúa cho vị anh hùng nào có thể đưa nàng trở về thành đô an toàn. Vì muốn trở thành phò mã, ngochuy quyết tâm khởi hành từ kinh đô, lên đường tiêu diệt quái vật giải cứu công chúa.

Sơ đồ khu Rừng Thiêng được biểu diễn bằng một lưới ô vuông có kích thước \(M\times N\), với ô góc trên bên trái chính là đế quốc ByteLand và ô góc dưới bên phải là hang ổ bọn quái vật. Các ô còn lại thể hiện các khu vực khác nhau trong khu rừng. Mỗi ô trên lưới được biểu diễn bằng một số nguyên dương, chính là độ nguy hiểm có thể bị gây ra bởi địa hình và quái vật sống ở khu đó. Năng lực con người là có hạn, ngochuy không thể tiêu diệt hết toàn bộ quái vật trong khu rừng, chính vì vậy anh muốn tính xem có bao nhiêu cách tiến đến hang ổ để đánh bại quái vật giải cứu công chúa sao cho tổng sức mạnh của quái vật trên đường đi không vượt quá chỉ số năng lực của anh. Do không có khả năng lập trình nên ngochuy muốn nhờ đến sự giúp đỡ của các bạn IT.

Biết rằng ở mỗi lần di chuyển, ngochuy sẽ tiến qua khu vực ở bên phải hoặc ở ngay dưới khu vực mình đang đứng và độ nguy hiểm của kinh đô luôn bằng \(0\). Cần tính số đường đi có thể từ ô \((1,\ 1)\) đến ô \((M,\ N)\). Vì kết quả có thể rất lớn nên bạn chỉ cần tính và in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Dòng đầu chứa \(3\) số nguyên dương \(M,\ N,\ P\) - lần lượt là số hàng, số cột của lưới ô vuông và chỉ số năng lực của ngochuy;
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo sẽ chứa \(N\) số nguyên dương \(c_{i,1},\ c_{i,2},\ldots,c_{i,N}\) thể hiện độ nguy hiểm của từng khu vực.

Output

• In ra số phương án có thể của ngochuy modulo \(10^9+7\).

Ví dụ

Sample input

4 5 20
0 7 3 2 1
5 4 6 8 2
1 2 4 2 1
3 5 2 1 1

Sample output

10

Ràng buộc

• \(1\leq M,\ N\leq100\);
• \(1\leq P\leq10000\);
• \(0\leq c_{i,j}\leq100\);
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(1\leq M,\ N\leq20\).