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 đã rất chú trọng nội dung Toán học. 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 đã 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 ~⌊x⌋~ là số nguyên lớn nhất không vượt quá số thực x (làm tròn xuống), hãy tính: $$S = (a * 1 + b * ⌊\sqrt{1}⌋) + (a * 2 + b * ⌊\sqrt{2}⌋) + ... + (a * n + b * ⌊\sqrt{n}⌋)$$

Dữ liệu:

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

Kết quả:

Một số nguyên là phép chia lấy dư của tổng S cho ~(10^9 + 7)~.

Ràng buộc:

Có 40% số lượng test ứng với 40% số điểm thỏa mãn: ~n ≤ 100; a, b ≤ 100~;
Có 30% số lượng test khác ứng với 30% số điểm thỏa mãn: ~n ≤ 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 ≤ 10^{12}~.

Sample Input 1:

3 1 2

Sample Output 1:

12

Sample Input 2:

7 5 8

Sample Output 2:

228