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):

S(n) = 1^3+ 2^3 + 3^3+...+ n^3

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.

Dữ liệu vào: Đọc từ bàn phím (thiết bị vào chuẩn):

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

Kết quả: Ghi ra màn hình (thiết bị ra chuẩn):

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

Ví dụ:

Input 01:

3

Output 01:

36

Giải thích: 1^3 + 2^3 + 3^3 = 36; 36 mod 2026^2 = 36

Input 02:

10

Output 02:

3025

Ràng buộc:

• Có 50% số điểm tương ứng với 1 < N ≤ 10.

• Có 30% số điểm tương ứng với 10 < N ≤ 10^2.

• Có 20% số điểm còn lại tương ứng với 10^2 < N ≤ 10^12.