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_{ij}~. Ở 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~.

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_{ij}=1+[(a_i+b_j)\ mod\ k];\ \forall i \in [1;m],\ j \in [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)~.

Input:

Vào từ file văn bản JUMP.INP gồm:

• 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,a_3,\dots,a_m~ ~(0 \le a_i \le 10^9)~
• Dòng thứ ba chứa ~n~ số nguyên ~b_1,b_2,b_3,\dots,b_n~ ~(0 \le b_i \le 10^9)~

Output:

Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm được lấy theo module ~10^9 + 7~.

Ví dụ 1:

JUMP.INP

3 2 1
3 4 11
2 5

JUMP.OUT

3

Ví dụ 2:

JUMP.INP

3 2 2
3 4 11
2 5

JUMP.OUT

4

Subtask:

• ~15\%~ số test tương ứng ~15\%~ số điểm có ~m,n \le 10,\ k=1~
• ~15\%~ số test khác tương ứng ~15\%~ số điểm có ~m,n \le 10^3,\ k=1~
• ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~m,n \le 10^3,\ k \le 10~
• ~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.