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) / 2~

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ả

28

Giải thích

Ta có:

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