Nhảy về đích

Xét bảng hình chữ nhật kích thước $m\times n$ ô. Các hàng được đánh số từ $1$ đến $m$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái qua phải. Ô nằm trên hàng $i$ và cột $j$ được ghi một số nguyên không âm ký hiệu $C_{i,j}$. Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột.
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại.
• Chỉ được di chuyển trong phạm vi bảng đang xét.

Kích thước của bước nhảy từ ô $(i,j)$ tới ô $(u,v)$ được tính bằng giá trị $u+v-i-j$. Mỗi bước nhảy phải đưa quân cờ sang một ô khác, tức là có kích thước ít nhất $1$. Hai cách di chuyển được coi là khác nhau nếu dãy các ô mà quân cờ lần lượt đứng trong hai cách đó khác nhau.

Yêu cầu: Cho dãy $a_1,a_2,\dots ,a_m,b_1,b_2,\dots ,b_n$ và số nguyên dương $k$. Bảng $C$ kích thước $m\times n$ được xác định với $C_{i,j}=1+[(a_i+b_j)modk]$ với mọi $i=1÷m$; $j=1÷n$. Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái $(1,1)$ xuống ô dưới phải $(m,n)$.

Dữ liệu vào

• Dòng đầu chứa $3$ số nguyên dương $m,n,k$ ($m,n,k\le 4·{10}^3$).
• Dòng thứ hai chứa $m$ số nguyên $a_1,a_2,\dots ,a_m$ ($0\le a_i\le {10}^9$).
• Dòng thứ ba chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$ ($0\le b_j\le {10}^9$).

Dữ liệu ra

In ra một số nguyên duy nhất là số cách di chuyển tìm được lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le m,n,k\le 4·{10}^3$.
• $0\le a_i,b_j\le {10}^9$.

Subtasks

• Có $15\%$ số test tương ứng $15\%$ số điểm có $m,n\le 10$, $k=1$.
• Có $15\%$ số test khác tương ứng $15\%$ số điểm có $m,n\le {10}^3$, $k=1$.
• Có $20\%$ số test khác tương ứng $20\%$ số điểm có $m,n\le {10}^3$, $k\le 10$.
• Có $20\%$ số test khác tương ứng $20\%$ số điểm có $m,n\le {10}^3$.
• $30\%$ số test còn lại tương ứng $30\%$ số điểm không có ràng buộc gì thêm.

Ví dụ