Lưu ý: hiện tại bài đang lỗi không thể chấm bằng file .inp .out, nên các bạn không cần freopen mà chỉ cần nhập bằng màn hình và in ra màn hình thôi nhé

Sau khi sáp nhập, tỉnh Quảng Trị có quy mô dân số và diện tích tương đối lớn cùng với nhiều dư địa để phát triển. Với mục tiêu hiện đại hóa ngành nông nghiệp tỉnh nhà, hợp tác xã SEPA đã huy động các nông dân hợp tác với nhau để xây dựng những cánh đồng chuyên canh lớn, trong đó có cánh đồng chuyên trồng lúa hữu cơ được chia thành lưới gồm \(M \times N\) thửa ruộng hình vuông. Để thuận tiện trong việc áp dụng công nghệ cao vào sản xuất, các thửa ruộng trong lưới được đánh chỉ số hàng từ 1 đến \(M\) (từ trên xuống dưới) và chỉ số cột từ 1 đến \(N\) (từ trái qua phải), lúc này mỗi thửa ruộng sẽ được xác định thông qua một cặp chỉ số \((i, j)\) cho biết thửa ruộng nằm ở hàng \(i\) và cột \(j\).

Thật không may khi cánh đồng lúa xuất hiện dịch rầy nâu, lúc đầu chỉ có một con rầy nâu ở thửa ruộng \((1,1)\), sau đó đã lây lan nhanh đến tất cả các thửa ruộng khác với số lượng càng tăng. Hợp tác xã đã sử dụng một thiết bị bay thông minh để khảo sát mật độ rầy nâu trên các thửa ruộng, kết quả cho thấy hiện tại mỗi thửa ruộng ở hàng \(i\) và cột \(j\) có \(i \times j\) con rầy nâu.

Để diệt rầy nâu, hợp tác xã đã sử dụng \(P\) thiết bị bay không người lái đặc biệt, mỗi thiết bị có thể thực hiện tiêu diệt toàn bộ rầy nâu trong phạm vi lưới con hình chữ nhật gồm các thửa ruộng trong cánh đồng. Lãnh đạo hợp tác xã muốn biết sau khi sử dụng \(P\) thiết bị này thì số lượng rầy nâu còn lại chưa bị tiêu diệt là bao nhiêu.

Yêu cầu

Hãy tính số \(Q\) là số lượng rầy nâu còn lại chưa bị tiêu diệt.

Dữ liệu

Cho trong tệp SEPA.INP có cấu trúc như sau:

• Dòng đầu tiên chứa ba số nguyên \(M, N, P\) (\(1 \le M, N \le 10^9\); \(1 \le P \le 10\)).
• Dòng thứ \(i\) trong \(P\) dòng tiếp theo, chứa bốn số nguyên dương \(x1_i, y1_i, x2_i, y2_i\) (\(1 \le x1_i \le x2_i \le M\); \(1 \le y1_i \le y2_i \le N\)) cho biết thiết bị \(P_i\) đã diệt rầy nâu trong lưới con hình chữ nhật với thửa góc trên bên trái là \((x1_i, y1_i)\) và thửa góc dưới bên phải là \((x2_i, y2_i)\).

Kết quả

Ghi ra tệp SEPA.OUT một dòng chứa số nguyên duy nhất là phần dư của phép chia \(Q\) cho \(10^9+7\).

Ví dụ

SEPA.INP

3 4 1
2 2 3 4

SEPA.OUT

15

Giải thích: Có 6 thửa ruộng chưa được diệt rầy nâu là: \((1,1), (1,2), (1,3), (1,4), (2,1), (3,1)\) lần lượt có số rầy nâu là: \(1, 2, 3, 4, 2, 3\). Tổng số rầy nâu chưa bị diệt là \(15\).

Ràng buộc

• Subtask 1 (40% số test tương ứng 40% số điểm): \(1 \le M, N \le 10^3\); \(P = 1\).
• Subtask 2 (30% số test tương ứng 30% số điểm): \(1 \le M, N \le 10^9\); \(1 \le P \le 2\) và \(P\) lưới con hình chữ nhật không chồng lấn lên nhau.
• Subtask 3 (30% số test tương ứng 30% số điểm): không có ràng buộc gì thêm.