Cho số nguyên không âm ~n~.

Xét hàm:

~S(n) = 1² + 2² + 3² + ... + n²~

Hãy tính giá trị của ~S(n)~ bằng phương pháp đệ quy.

Chú ý:

Mặc dù có thể tính nhanh bằng công thức:

~S(n) = n × (n + 1) × (2n + 1) / 6~

nhưng trong bài toán này bạn phải sử dụng đệ quy.

Dữ liệu vào

• Dòng duy nhất chứa số nguyên ~n~.

Ràng buộc

• ~0 ≤ n ≤ 1000~.

Kết quả

In ra giá trị của ~S(n)~.

Ví dụ

Dữ liệu vào

7

Kết quả

140

Giải thích

Ta có:

~S(7) = 1² + 2² + 3² + 4² + 5² + 6² + 7²~

~= 1 + 4 + 9 + 16 + 25 + 36 + 49~

~= 140~.