Трудолюбивый Farmer John хочет четырёхсторонний забор для коров. Доску целой длины $N$ ($4\le N\le2,500$) он разрежет в трёх местах на четыре целые части.

Длины — любые положительные целые, если получается четырёхугольный забор. Сколько подходящих способов разрезать доску?

Примечания

• Способы различаются, если один имеет разрез там, где другой нет. Не исключайте симметрии и подобные сложности.
• Однако площадь забора должна быть больше $0$.
• Радуйтесь: ответ помещается в знаковое 32-битное целое.

Входные данные

• Строка 1: целое $N$.

Выходные данные

• Строка 1: целое число разрезаний на четыре части, образующие допустимый четырёхугольник.

Примеры

Входные данные 1

6

Выходные данные 1

6

Примечание

Длина доски 6.

Есть 10 способов получить четыре части: $(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)$. Но следующие четыре не образуют четырёхугольник: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.

Подзадачи

Баллы: 250.

Автор задачи: Jeffrey Wang, 2007