Farmer John cắt từ đồng cỏ gần như vô hạn mảng cỏ vuông với mọi độ dài cạnh nguyên. Đôi khi FJ không bật lưỡi cắt đúng và làm cả mảng cạnh 0. Ông xếp thành đống gọn, Bessie thấy vào một buổi chiều.

Bessie luôn muốn cỏ ngon ở đồng bí mật. Cô chọn mang đúng bốn mảng, cắt thành phần $1\times1$ để lát $N$ ô vuông đơn vị ($1 \le N \le 10,000$).

Có bao nhiêu cách chọn bốn mảng để lát đồng? Với kích thước 4 có năm: $(1,1,1,1)$, $(2,0,0,0)$, $(0,2,0,0)$, $(0,0,2,0)$, $(0,0,0,2)$. Thứ tự tính: $(4,3,2,1)$ khác $(1,2,3,4)$.

Dữ liệu vào

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

Dữ liệu ra

• Dòng 1: một số nguyên, số cách khác nhau Bessie chọn bốn mảng cỏ cho đồng.

Ví dụ

Dữ liệu vào 1

4

Dữ liệu ra 1

5

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