题目描述

勤奋的Farmer John想给他的牛场建造一个四边形的围栏.他有一块长度为整数N (4 <= N <= 2500) 的木板.他希望在三个点上切开这块木板,把它变成长度均为整数的四块小木板.

这四块木板的长度可以是任意的正整数,只要Farmer John能够用它们组成一个四边形.那么,他有多少种不同的切割木板的方法?

注意

• 只要有一个切割点不同,那么两种切割方式就不同.不用考虑对称之类的复杂情况.

• 可以确定的是,木板的长度肯定大于0.

• 答案在32位整数类型可以储存的范围内.

输入格式

第1行: 一个正整数N.

输出格式

• 第1行: 一个正整数,表示有多少种可行的切割方式.

样例数据

input

6

output

6

Farmer John有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)四种方式不能构成四边形.

数据规模与约定

usaco Oct09。

时间限制：$1 text {s}$

空间限制：$256 text {MB}$