지정좌석 배치하기 2

이 문제는 지정좌석 배치하기 1 문제와 마지막 문단 및 출력만 다릅니다. 이 문제의 코드로 지정좌석 배치하기 1 문제를 해결할 수 없음에 유의하세요.

UDP대학교의 인기 교수 달구 교수님의 이번 학기 강의실은 정원이 $N \times M$명인 강의실로 배정되었으며, $N$행 $M$열의 직사각형 모양으로 좌석이 배치되어 있다. 해당 강의실은 뒤에 앉은 학생도 원활히 강의를 수강할 수 있도록 각 행의 좌석 높이가 $D$씩 차이가 나며, 가장 앞에 위치한 행부터 뒤에 위치한 행까지 순서대로 $1$행, $2$행, $\cdots$, $N$행이라고 할 때 $i$행의 좌석 높이는 $D\times i$이다.

달구 교수님은 원활한 출석체크를 위해 지정좌석제를 실시하기 때문에, $N \times M$명의 모든 학생은 한 학기 동안 동일한 좌석에만 앉을 수 있다. 달구 교수님은 학생들이 최대한 본인이 원하는 좌석에 앉을 수 있도록 각 학생이 희망하는 좌석의 행을 조사하였고, 그 결과 각 행에 앉기를 희망하는 학생들을 $M$명씩 선정하였다. 그중 $i$행의 좌석을 희망하는 학생의 키는 각각 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$이다.

학생들의 원활한 강의 수강을 위해, 각 학생의 시야가 같은 열에 앉은 다른 학생에 의해 가려지는 경우가 없도록 좌석을 배치하고자 한다. 구체적으로, 각 학생의 (좌석 높이 + 키)는 자신보다 앞 행의 같은 열에 있는 모든 학생의 (좌석 높이 + 키)보다 커야 한다.

좌석을 배치하던 달구 교수님은 문득 주어진 조건에 맞게 모든 학생을 원하는 행의 좌석에 배치하는 경우의 수가 궁금해졌다. 달구 교수님의 궁금증을 해결해 주기 위해, 주어진 조건에 맞게 모든 학생을 원하는 행의 좌석에 배치하는 경우의 수를 구해주자. 단, 경우의 수가 너무 커질 수 있으므로 경우의 수를 $10^9 + 7(=1\,000\,000\,007)$로 나눈 나머지를 구해주자.

첫 번째 줄에 강의실 좌석의 행 개수 $N$, 열 개수 $M$과 각 행의 높이 차이를 의미하는 정수 $D$가 공백으로 구분되어 주어진다. $(1\leq N, M\leq 1\,000;$ $1\leq D\leq 100\,000)$

이후 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$행 좌석에 앉고자 하는 학생 $M$명의 키를 의미하는 정수 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$이 공백으로 구분되어 주어진다. $(1\leq h_{i,j}\leq 100\,000)$

주어진 조건에 맞게 모든 학생을 원하는 행의 좌석에 배치하는 경우의 수를 $10^9+7(=1\,000\,000\,007)$로 나눈 나머지를 출력한다.