Chào mọi người nha! Em là thằng nhóc lớp 8 chuyên Tin mới được tuyển vào làm chân chạy vặt, test đề cho ban tổ chức Magellan Contest 2026 nè.
Hôm nay em phải lên đây kể cho các bác nghe quả drama siêu to khổng lồ, gay cấn hơn cả phim hành động vừa mới xảy ra trong phòng họp Discord kín của ban tổ chức. Một câu chuyện kết hợp giữa lịch sử hàng hải, toán học bão táp, và màn đấu trí cực gắt giữa hai thần tượng của em là anh ledinhbaonam và anh trongphithien để tạo ra siêu phẩm "Bài 5" cho contest lần này!

Chuyện là thế này, tuần trước ban tổ chức chúng em họp để chốt đề cho contest. Ý tưởng xuyên suốt là mô phỏng lại chuyến đi của hạm đội Armada de Molucca qua các đại dương.

Đến lượt thiết kế Bài 5 – bài quyết định xem ai sẽ là nhà vô địch – thì anh trongphithien hào hứng share màn hình Discord, đưa ra một bài toán mà anh ấy tự khen là "siêu lãng mạn":

Ý tưởng của em là thế này: Tàu của Magellan xuất phát từ vĩ độ \(1\) đến vĩ độ \(N\). Tại mỗi vĩ độ \(i\), hạm đội sẽ gặp một số lượng hòn đảo bằng số ước của \(i\) (tức là \(d(i)\)). Thí sinh chỉ cần tính tổng số đảo mà Magellan có thể ghé thăm trên toàn bộ chuyến đi: \(S = \sum_{i=1}^N d(i)\) với giới hạn \(N \le 10^{12}\).

Nghe xong, em đang gặm dở cái đùi gà mà suýt rơi cả ra ngoài vì bài này... quen quá! Quả nhiên, anh ledinhbaonam vừa nhìn qua một phát là thở dài thườn thượt, giọng đầy sự bất lực gõ mic bôm bốp:

Này trongphithien, mày làm đề thế này thì học sinh nó 'cook' sạch trong 5 phút à? Cái công thức tính tổng số ước số \(\sum d(i)\) dùng công thức chia căn \(\lfloor N/i \rfloor\) từ thời Napoléon cởi truồng tắm mưa rồi! Với lại đây là Magellan Contest, đi biển phải có bão tố, phải có sóng thần chứ dễ thế ai chơi?!

Anh trongphithien gãi đầu gãi tai, ấm ức bảo:

Nhưng em muốn nó liên quan đến lịch sử! Magellan đi vòng quanh Trái Đất, tức là quỹ đạo của ông ấy có tính tuần hoàn và phản chiếu song song qua đường xích đạo mà anh ledinhbaonam!

Đầu anh ledinhbaonam nảy số với tốc độ ánh sáng. Anh ấy đập bàn cái rầm, mắt sáng lên như đèn pha:

Ý tưởng 'phản chiếu song song' của mày hay đấy trongphithien! Nếu quỹ đạo phản chiếu, ta không dùng vĩ độ \(i\) nữa, mà ta bắt Magellan phải đi qua các tọa độ bình phương \(i^2\)! Lúc này, tại mỗi điểm dừng chân \(i\) từ \(1\) đến \(N\), số lượng hòn đảo san hô (hoặc luồng lạch an toàn để neo đậu) xung quanh sẽ là số ước số của vĩ độ bình phương: \(d(i^2)\)!
Thí sinh sẽ phải giúp Magellan tính toán tổng số lượng luồng lạch an toàn trên toàn bộ \(N\) trạm dừng chân để lập bản đồ cho hạm đội phía sau:

Với giới hạn thời gian chạy là 1.0 giây, bộ nhớ 256 MB, và cho \(N\) lên tới \(10^{11}\)! Như thế mới xứng tầm bài 5 của Magellan Contest chứ!

Anh trongphithien nghe xong mặt tái mét, lắp bắp:

Anh ledinhbaonam ơi, anh định làm khó thí sinh đến mức này sao?! \(N \le 10^{11}\) mà tính \(d(i^2)\) thì mấy cách duyệt hay tính toán thông thường khóc thét hết! Bài này khoai thế này sao mà chạy kịp trong 1 giây?!

Anh ledinhbaonam cười lớn đầy tự tin:

Thì thế mới là Magellan! Phải vượt qua bão táp eo biển mới tới được Thái Bình Dương! Mày không tin học sinh bây giờ out trình à? Giờ mày giải thích ví dụ cho thằng út nó hiểu để nó làm testcase đi!

Thế là anh trongphithien quay sang lôi bảng vẽ ra giải thích cho em với ví dụ siêu nhỏ \(N = 4\):

• Tại trạm \(i = 1\): tọa độ là \(1^2 = 1 \implies d(1) = 1\) (ước là \(\{1\}\))
• Tại trạm \(i = 2\): tọa độ là \(2^2 = 4 \implies d(4) = 3\) (ước là \(\{1, 2, 4\}\))
• Tại trạm \(i = 3\): tọa độ là \(3^2 = 9 \implies d(9) = 3\) (ước là \(\{1, 3, 9\}\))
• Tại trạm \(i = 4\): tọa độ là \(4^2 = 16 \implies d(16) = 5\) (ước là \(\{1, 2, 4, 8, 16\}\))
• Tổng cộng số luồng lạch an toàn là: \(1 + 3 + 3 + 5 = 12\). Output sẽ là 12.

Em nghe xong gật gù hiểu ra vấn đề, liền nhận nhiệm vụ phụ tá. Hai đại ca lao vào code quên ăn quên ngủ. Anh trongphithien thì cặm cụi viết code trâu bằng Python để chạy các testcase nhỏ \(N \le 10^6\) làm bộ dữ liệu đối chiếu, còn anh ledinhbaonam thì gõ C++ lo phần thuật toán quy hoạch động tối ưu để gánh trọn giới hạn \(N = 10^{11}\).

Thực ra bài này cũng khá đơn giản thôi! Tóm cái váy lại thì đây là phần nhiệm vụ:

Nhiệm vụ

• Cho số nguyên dương \(N\). Hãy tính giá trị của tổng sau:

• Trong đó, \(d(x)\) là số lượng ước số nguyên dương của \(x\).

Input

• Một dòng duy nhất chứa số nguyên \(N\) (\(1 \le N \le 10^{11}\)).

Output

• Một số nguyên duy nhất là kết quả của \(S \pmod{10^9+7}\).

4

12

100

1194

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le N \le 10^7\)
• Subtask 2 (\(60\%\) số điểm): Không có ràng buộc nào thêm