TLEoj Cup Final Day 2 - Diện tích hình chữ nhật

Điểm: 1700 (thành phần)

Thời gian: 1.75s

Bộ nhớ: 256M

Input: RECT.inp

Output: RECT.out

Tác giả:

Sunlight

Dạng bài

khanhphucscratch có một mảnh giấy hình chữ nhật kích thước $n \times m$ được chia thành các ô vuông đơn vị và muốn tính diện tích của tất cả các hình chữ nhật con (hình chữ nhật nằm gọn trong tờ giấy) có các cạnh song song với các cạnh của tờ giấy và bao trọn các ô vuông đơn vị. Thật không may, sau khi tính toán một vài phép tính cơ bản, khanhphucscratch nhận ra kết quả bài toán có thể rất lớn, nên muốn nhờ các bạn cùng tính để biết mình đúng hay sai. Các bạn hãy giúp khanhphucscratch nhé.

Input, Output và Subtask

Input (RECT.inp)

Dòng đầu tiên gồm số nguyên dương $q \le 100$ là số trường hợp kiểm thử.
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $m, n \le 10^9$ .

Output (RECT.out)

Gồm $q$ dòng, mỗi dòng gồm một số nguyên là tổng diện tích các hình chữ nhật con thỏa mãn đề bài sau khi chia lấy dư cho $10^9 + 7$ .

Subtask

$20\%$ số điểm có $n, m \le 10$ .
$20\%$ số điểm khác có $n, m \le 100$ .
$20\%$ số điểm khác có $n, m \le 1000$ .
$20\%$ số điểm khác có $n \le 1000$ .
$20\%$ số điểm khác không có giới hạn gì thêm.

Sample 1

Input (RECT.inp)

2
2 3
5 8

Output (RECT.out)

40
4200

Notes

Ở ví dụ thứ nhất, hình chữ nhật $2 \times 3$ có các hình chữ nhật con với kích thước và số lượng như sau:
- $1 \times 1$ : $6$ hình.
- $1 \times 2$ : $3$ hình.
- $1 \times 3$ : $2$ hình.
- $2 \times 1$ : $4$ hình.
- $2 \times 2$ : $2$ hình.
- $2 \times 3$ : $1$ hình.

Bình luận

Không có bình luận nào.