Xét bảng hình chữ nhật kích thước m×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,…,a_m, b_1,b_2,…,b_n và số nguyên dương k. Bảng C kích thước m×n được xác định với C_ij=1+[(a_i+b_j ) mod k] ∀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:

Dòng đầu chứa 3 số nguyên dương m,n,k (m,n,k≤4.10^3)

Dòng thứ hai chứa m số nguyên a_1,a_2,a_3,…,a_m (0≤a_i≤10^9)

Dòng thứ ba chứa n số nguyên b_1,b_2,b_3,…,b_n (0≤b_i≤10^9)

Kết quả:

ghi ra 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.

Sample Input

3 2 1
3 4 11
2 5

Sample Output

3

Giới hạn

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