Cho một bảng ô vuông gồm \(N\) hàng và \(M\) cột. Các hàng được đánh số từ \(1\) đến \(N\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(M\) từ trái sang phải.

Ô thuộc hàng thứ \(i\) và cột thứ \(j\) được gọi là ô \((i, j)\) và có trọng số \(a_{i,j}\).

Ban đầu, có một con kiến đứng tại ô \((1, 1)\). Trong mỗi nước đi, con kiến có thể di chuyển sang ô kề cạnh bên phải hoặc ô kề cạnh bên dưới. Con kiến không thể đi ra khỏi bảng.

Bạn được cho một số nguyên dương \(X\). Hãy đếm số đường đi từ ô \((1, 1)\) đến ô \((N, M)\) sao cho trọng số lớn nhất mà con kiến đi qua trên đường đi đúng bằng \(X\).

Vì kết quả có thể rất lớn, hãy in ra đáp án sau khi lấy phần dư khi chia cho \(16102008\).

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N, M, X\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(M\) số nguyên dương \(a_{i,1}, a_{i,2}, \dots, a_{i,M}\).

Output

• In ra một số nguyên duy nhất là số đường đi thỏa mãn, lấy modulo \(16102008\).

Example

3 3 2
1 1 1
1 2 1
1 1 1

4

Scoring

• Trong mọi test, \(1 \le a_{i,j}, X \le 10^9\) với mọi \(1 \le i \le N, 1 \le j \le M\).
• Subtask \(1\) (\(10\%\) số điểm): \(N, M \le 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(N = 1, M \le 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(N, M \le 1000\) và \(a_{i,j} = X\) với mọi ô \((i, j)\).
• Subtask \(4\) (\(20\%\) số điểm): \(N, M \le 1000\) và chỉ tồn tại đúng một ô \((i, j)\) thỏa mãn \(a_{i,j} = X\).
• Subtask \(5\) (\(30\%\) số điểm): \(N, M \le 1000\).