Bài toán

Cho bảng số có kích thước N × N được điền số liên tiếp từ 1 đến N², từ trái qua phải, từ trên xuống dưới. Ví dụ với N = 4, bảng số như sau:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

Yêu cầu:

Cho vị trí một ô ở dòng thứ x và cột thứ y, hãy tính tổng hai đường chéo đi qua ô này.

Dữ liệu vào từ thiết bị vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên dương N và Q (N ≤ 10⁹; Q ≤ 10⁵) mô tả kích thước của bảng số và số lượng truy vấn;
• Q dòng sau, mỗi dòng gồm hai số nguyên dương x và y (x, y ≤ N) mô tả một truy vấn là vị trí một ô ở dòng thứ x và cột thứ y.

Kết quả ghi ra thiết bị ra chuẩn:

• Gồm Q dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.
• Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả cho 10⁹ + 7.

Ví dụ:

Dữ liệu vào:

4 2
2 2
1 3

Kết quả ra:

46
26

Giải thích:

• Truy vấn (2,2) đi qua các ô: 1 + 6 + 11 + 16 và 3 + 6 + 9 = 46 (trừ trùng 6 một lần).
• Truy vấn (1,3) đi qua các ô: 3 + 6 + 9 = 18 và 1 + 6 + 11 = 26 (trừ trùng 6 một lần).

Ràng buộc:

• Có 70% số test ứng với 70% số điểm có: N ≤ 100; Q = 1;
• 20% số test khác ứng với 20% số điểm có: N ≤ 5000; Q ≤ 10⁵;
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.