지정좌석 배치하기 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$로 나눈 나머지를 구하세요.

첫 번째 줄에 $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)$로 나눈 나머지를 출력합니다.