Chiến thắng

Để tiêu diệt một vật thể có dạng khối lập phương, người chơi cần tiêu tốn một năng lượng tương ứng bằng thể tích của khối lập phương đó. Ví dụ: để tiêu diệt khối lập phương có cạnh là \(2\), người chơi cần tiêu tốn \(8\) năng lượng.

Ban đầu, trên màn hình xuất hiện khối lập phương có độ dài cạnh là \(1\) để người chơi tiêu diệt. Sau khi tiêu diệt xong, màn hình tiếp tục hiển thị khối vật thể lập phương có độ dài cạnh của khối lập phương được tiêu diệt trước đó tăng lên \(1\) đơn vị. Quá trình này lặp đi lặp lại cho đến khi người chơi tiêu diệt được khối lập phương có độ dài cạnh là \(N\) thì giành chiến thắng.

Yêu cầu: Hãy cho biết người chơi cần tiêu tốn bao nhiêu năng lượng để vượt qua thử thách và giành chiến thắng?

Input

Dữ liệu vào:chứa duy nhất một số nguyên dương \(N\) (\(0 < N \le 10^{16}\)) là độ dài cạnh của khối lập phương cuối cùng cần phải tiêu diệt.

Ràng buộc:

• Subtask 1: có \(10/12\) số test tương ứng với \(5{,}0\) điểm với \(0 < N \le 10^4\).

• Subtask 2: có \(2/12\) số test tương ứng với \(1{,}0\) điểm với \(10^4 < N \le 10^{16}\).

Output

In ra một số nguyên duy nhất là tổng năng lượng cần phải tiêu tốn để giành chiến thắng trò chơi. Do tổng năng lượng có thể khá lớn nên chỉ ghi nhận kết quả sau khi chia lấy dư cho \(10^8\).

Example 1

Input:

2

Output:

9

Example 2

Input:

3

Output:

36

Note

Với \(N = 2\): thể tích khối thứ nhất là \(1^3 = 1\), khối thứ hai là \(2^3 = 8\), nên cần tiêu tốn \(1^3 + 2^3 = 9\) năng lượng để giành chiến thắng.

Với \(N = 3\): cần tiêu tốn \(1^3 + 2^3 + 3^3 = 36\) năng lượng để giành chiến thắng.