题目描述

勤奋的 Farmer John 想要建造一个四面的栅栏来关住牛们。他有一块长为 $n$ 的木板，他想把这块木板切成四块。这四块小木板可以是任何一个正整数长度只要 Farmer John 能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。

注意：

• 只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况。
• 栅栏的面积要大于 $0$
• 整块木板都要用完。

输入格式

一行一个整数 $n$ 。

输出格式

一个整数表示合理的方案总数。

样例输入

6

样例输出

6

样例说明

Farmer John 能够切出所有的情况为:

$(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)$ 不能够组成一个四边形。

数据规模与约定

对于 $100\%$ 的数据，保证$\ 4 \leq n \leq 2500$，保证答案在 long long 范围内。

题目来源

资格赛