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~.

Input

• Dữ liệu vào từ thiết bị vào chuẩn gồm ba số nguyên ~n, a, b~.

Output

• Kết quả ghi ra thiết bị ra chuẩn một số nguyên là tổng ~S~ chia dư cho ~(10^9 + 7)~.

Sample Input 1

3 1 2

Sample Output 1

12

Subtasks

• 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}~.