Bình là một học sinh lớp 7, cậu ấy vừa được học công thức tính tổng của các số từ 1 đến n. Bình rất thích thú vị chỉ nhờ 1 công thức mà có thể tính toán được cả dãy số rất dài. Và cậu tự đặt ra câu hỏi: "Làm thế nào để tính được tổng của các số từ \(1^2\) đến \(n^2\). Bạn hãy giúp Bình giải quyết vấn đề này nhé.

Yêu cầu: Tính tổng \(1^2 + 2^2 + ... + n^2\) rồi mod cho \(10^9 + 7\)

Dữ liệu: Nhập vào từ bàn phím số nguyên dương \(n\)

Kết quả: In ra tổng theo yêu cầu bài toán

Input

3

Output

14

Subtask 1 (40%): Số điểm có \(n \le 10^3\)

Subtask 2 (30%): Số điểm có \(n \le 10^6\)

Subtask 2 (30%): Số điểm có \(n \le 10^9\)