Hai hình chữ nhật rời nhau

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C++, Java, Python

Cho một lưới gồm ~n~ hàng và ~m~ cột ô vuông đơn vị. Một hình chữ nhật là một khối ô liên tiếp theo hàng và cột, chứa ít nhất một ô.

Hãy đếm số cách chọn hai hình chữ nhật không có ô chung. Hai hình được phép chạm nhau ở biên, miễn là không dùng chung ô. Cặp hình chữ nhật (~A~, ~B~) và (~B~, ~A~) được tính là cùng một cách.

Cấu hình Input
  • Một dòng chứa hai số nguyên ~n~ và ~m~ — lần lượt là số hàng và số cột của lưới.
Cấu hình Output
  • In ra số cách chọn modulo ~10⁹ + 7~.
Giới hạn
  • ~1 ≤ n, m ≤ 10⁷~.
Ví dụ

Input

1 3

Output

5

Giải thích: Trên lưới một hàng và ba cột, có 5 cặp hình chữ nhật rời nhau: ba cặp gồm hai ô đơn, ô thứ nhất cùng đoạn từ cột 2 đến 3, và đoạn từ cột 1 đến 2 cùng ô thứ ba.

Subtasks
Subtask Ràng buộc Điểm
1 ~1 ≤ n, m ≤ 3~ 10 điểm
2 ~1 ≤ n, m ≤ 10³~ 20 điểm
3 ~1 ≤ n, m ≤ 2 × 10⁵~ 30 điểm
4 ~1 ≤ n, m ≤ 10⁷~ 40 điểm

Các test được chấm độc lập; không áp dụng chấm theo batch.


Loading...