Trong lễ khai mạc Hội xuân tại quảng trường Võ Nguyên Giáp (tỉnh Thái Nguyên), Ban tổ chức có một phần quà đặc biệt dành cho các bạn học sinh yêu thích toán học và lập trình. Thử thách đưa ra như sau:

Cho một số nguyên dương \(n\). Bạn cần tính tổng lập phương của tất cả các số tự nhiên từ \(1\) đến \(n\). Ký hiệu tổng này là \(S(n)\):

Vì kết quả \(S(n)\) có thể rất lớn, Ban tổ chức chỉ yêu cầu bạn in ra phần dư của \(S(n)\) khi chia cho \(2026^2\).

Yêu cầu: Hãy lập trình giúp các bạn học sinh giải quyết thử thách trên để nhận phần quà từ Ban tổ chức.

Input

• Một số nguyên dương \(n\) (\(1 \le n \le 10^{12}\)).

Output

• Số nguyên duy nhất là giá trị \(S(n) \mod 2026^2\) (mod là phép chia lấy phần dư).

Example

3

36

10

3025

Scoring

• Có \(50\%\) số điểm tương ứng với \(1 \le n \le 10\).
• Có \(30\%\) số điểm tương ứng với \(10 < n \le 10^2\).
• Có \(20\%\) số điểm còn lại tương ứng với \(10^2 < n \le 10^{12}\).