Farmer John chăm chỉ muốn hàng rào bốn cạnh cho bò. Ông cắt ván dài nguyên $N$ ($4\le N\le2,500$) tại ba điểm để có bốn đoạn dài nguyên.

Độ dài có thể là bất kỳ số nguyên dương nếu tạo được tứ giác. Có bao nhiêu cách cắt để làm hàng rào hoàn chỉnh?

Chú ý

• Hai cách khác nếu một có điểm cắt mà cách kia không có. Không loại đối xứng hay lo phức tạp tương tự.
• Nhưng diện tích phải lớn hơn $0$.
• Vui thay đáp án vừa số nguyên có dấu 32 bit.

Dữ liệu vào

• Dòng 1: số nguyên $N$.

Dữ liệu ra

• Dòng 1: số nguyên, số cách cắt bốn đoạn tạo tứ giác hợp lệ.

Ví dụ

Dữ liệu vào 1

6

Dữ liệu ra 1

6

Ghi chú

Ván dài 6.

Có 10 cách cắt bốn đoạn: $(1,1,1,3)$; $(1,1,2,2)$; $(1,1,3,1)$; $(1,2,1,2)$; $(1,2,2,1)$; $(1,3,1,1)$; $(2,1,1,2)$; $(2,1,2,1)$; $(2,2,1,1)$; $(3,1,1,1)$. Nhưng bốn cách sau không tạo tứ giác: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.

Nhiệm vụ con

Điểm: 250.

Tác giả bài toán: Jeffrey Wang, 2007