Assigned Seating 2

This problem differs from 지정좌석 배치하기 1 only in its last paragraph and its output. Code that solves 지정좌석 배치하기 1 cannot solve this problem.

Professor Dalgu, a popular instructor at UDP University, has been assigned a lecture hall with a capacity of $N \times M$ students. The seats form a rectangle of $N$ rows and $M$ columns. So that students in the back can follow the lecture, the seat height rises by $D$ for each row. Counting from the front, the rows are $1$ to $N$, and the seat height of row $i$ is $D \times i$.

Professor Dalgu uses assigned seats for easy attendance checks, so each of the $N \times M$ students sits in the same seat all semester. The professor surveyed which row each student wants and selected $M$ students for each row. Let $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$ be the heights of the students who want row $i$.

No student's view may be blocked by a student in the same column in an earlier row. Specifically, the seat height plus the student's height must be greater than the seat height plus the height of every student in the same column in an earlier row.

Professor Dalgu wants to know how many ways there are to seat all students in their requested rows while meeting this condition. Find the count modulo $10^9 + 7$.

The first line contains $N$, $M$, and $D$ separated by spaces. $(1 \leq N, M \leq 1\,000;\ 1 \leq D \leq 100\,000)$

The next $N$ lines contain the heights of the $M$ students who want row $i$, with line $i+1$ holding $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$ separated by spaces. $(1 \leq h_{i,j} \leq 100\,000)$

Print the number of ways to seat all students in their requested rows that meet the condition, modulo $10^9 + 7 (=1\,000\,000\,007)$.