Background

Hardworking Farmer John wants to build a fence with four sides to keep the cows inside. He now has a long wooden board of length $N$ ($4 \leq N \leq 2,500$). He needs to cut this board into four pieces, each with a positive integer length, so that he can build a fence.

Problem Description

How many different cutting methods are there such that the four cut boards can form a four-sided fence.

Note:

1. Do not consider symmetry. You do not need to remove symmetric cases or deal with other similar complicated issues.
2. The area enclosed by the fence must be greater than $0$.
3. The result fits in a 32-bit integer.

Input Format

One integer $N$.

Output Format

The number of ways Farmer John can split the board and make a quadrilateral.

6

6

Hint

Farmer John has $10$ ways to cut the board into four pieces:

• (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)。

Among them, there are four cases that cannot form a quadrilateral:

• (1, 1, 1, 3),
• (1, 1, 3, 1),
• (1, 3, 1, 1),
• (3, 1, 1, 1)。

Translated by ChatGPT 5