Tính tổng

Toán học đóng vai trò quan trọng trong Tin học. Khi thiết kế chương trình giảng dạy môn Tin học cho các lớp chuyên Tin theo chương trình giáo dục phổ thông mới (Chương trình giáo dục phổ thông 2018), thầy chủ biên chương trình Hồ Sĩ Đàm đã rất chú trọng nội dung toán. Chuyên đề đầu tiên mà học sinh sẽ học sau khi học xong ngôn ngữ lập trình là chuyên đề "Số học và tổ hợp". Tham gia kì thi Duyên Hải năm 2022, thầy Hồ Sĩ Đàm đã ra một bài toán như sau:

Cho số nguyên dương $n$ và hai số nguyên không âm $a,b$, kí hiệu $\lfloor x\rfloor$ là số nguyên lớn nhất không vượt quá $x$ (làm tròn xuống), hãy tính:

$$S=(a\times 1+b\times \lfloor \sqrt{1}\rfloor )+(a\times 2+b\times \lfloor \sqrt{2}\rfloor )+\dots +(a\times n+b\times \lfloor \sqrt{n}\rfloor )$$

Yêu cầu: Hãy tính tổng $S$.

Dữ liệu vào

Gồm ba số nguyên $n,a,b$.

Dữ liệu ra

In ra một số nguyên là tổng $S$ chia dư cho $({10}^9+7)$.

Ràng buộc

• $1\le n\le {10}^{12}$.
• $0\le a,b\le {10}^{12}$.

Subtasks

Điểm được tính theo từng test.

• Có $40\%$ số lượng test ứng với $40\%$ số điểm thỏa mãn: $n\le 100$; $a,b\le 100$.
• Có $30\%$ số lượng test khác ứng với $30\%$ số điểm thỏa mãn: $n\le {10}^{12}$; $a=1$; $b=0$.
• Có $30\%$ số lượng test còn lại ứng với $30\%$ số điểm thỏa mãn: $n,a,b\le {10}^{12}$.

Ví dụ