Một kim tự tháp như hình bên dưới được tạo bởi các số tự nhiên theo quy luật sau:

• Dòng đầu tiên chỉ gồm số ~1~;
• Dòng thứ ~i~ gồm các số tự nhiên liên tiếp từ ~1~ đến ~i~ rồi giảm dần về ~1~;

Tạo ra kim tự tháp thì không khó nhưng tính tổng kim tự tháp thì không hề đơn giản bởi mỗi dòng có quá nhiều số và phải thực hiện nhiều phép cộng nên Ban tổ chức muốn nhờ các thí sinh thi Tin học trẻ tính giúp. Hãy đưa ra tổng các số của kim tự tháp từ dòng ~1~ đến dòng ~N~.

Dữ liệu

• Một số tự nhiên ~N~ ~(N ≤ 10^9)~

Kết quả

• Đưa ra kết quả của bài toán.

Chấm điểm

• Nếu chương trình chạy đúng những trường hợp ~N ≤ 100~, thí sinh sẽ được ~40~ điểm;
• Nếu chương trình chạy đúng những trường hợp ~N ≤ 1000~, thí sinh sẽ được ~80~ điểm.
• Riêng với trường hợp ~1000 < N ≤ 10^9~, vì kết quả quá lớn nên thí sinh chỉ đưa ra phần dư của kết quả khi chia cho ~1009~. Trường hợp này chỉ chiếm ~20~ điểm.

Sample Input 1

2

Sample Output 1

5

Sample Input 2

5

Sample Output 2

55