Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Quang có ~n~ khối gỗ màu đỏ, mỗi khối có kích thước ~1 \times 1 \times a~ (cm) và ~m~ khối gỗ màu xanh, mỗi khối có kích thước ~1 \times 1 \times b~ (cm). Quang xếp các khối gỗ thành một cột thẳng đứng có đáy là một hình vuông kích thước ~1 \times 1~ (cm) và tiến hành đo chiều cao của cột gỗ, ký hiệu là ~h~. Quang thử tất cả các cách xếp khác nhau và ghi lại các giá trị ~h~ thu được.

Yêu cầu: Vì số lượng giá trị ~h~ mà Quang ghi lại được là quá lớn, bạn hãy giúp Quang đếm xem có bao nhiêu giá trị ~h~ khác nhau mà Quang đã tạo ra.

Dữ liệu vào

• Một dòng duy nhất gồm bốn số nguyên dương ~a, b, n, m~ ~(1 \le a, b, n, m \le 10^9)~.

Kết quả

• Một dòng duy nhất là số giá trị ~h~ khác nhau mà Quang tạo được. Vì số giá trị có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho ~10^9 + 7~.

Giới hạn

• Thời gian 1 giây. Đọc dữ liệu từ bàn phím, in ra màn hình.

Subtask

• ~20\%~ số điểm có ~n = m = 1~.
• ~20\%~ số điểm khác có ~a = b~.
• ~10\%~ số điểm khác có ~m = 1~.
• ~10\%~ số điểm khác có ~n, m \le 10~.
• ~10\%~ số điểm khác có ~n, m \le 1000~.
• ~10\%~ số điểm khác có ~b = 1~.
• ~10\%~ số điểm khác có ~m \le 10^5~.
• ~10\%~ số điểm còn lại không có giới hạn gì thêm.

Sample Input 1

2 3 1 2

Sample Output 1

5

Giải thích

Các giá trị ~h~ có thể tạo được là ~2, 3, 5, 6, 8~. Để tạo được giá trị ~h = 6~, có thể chồng hai khối gỗ màu xanh lên nhau; để tạo được giá trị ~h = 5~, có thể chồng một khối gỗ màu đỏ lên một khối gỗ màu xanh.

Sample Input 2

3 3 1 1

Sample Output 2

2

Giải thích

Có thể tạo ra được 2 giá trị ~h = 3~ và ~h = 6~.

Nguồn: Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 1.