Building a Fence

Farmer John wants to build a four-sided fence to enclose his cows. He has a single plank of wood of integer length $N$ ($4 \le N \le 2500$). He will cut it at three points to produce four pieces, each of positive integer length.

The four pieces may have any positive integer lengths, as long as they can be arranged into a quadrilateral fence with strictly positive area. In how many different ways can he cut the plank so that the four resulting pieces form a valid fence?

Notes:

• Two ways of cutting are different if one has a cut at a position where the other does not. Do not eliminate rotations, reflections, or other symmetric duplicates.
• The fence must enclose an area greater than $0$.
• The answer always fits in a signed 32-bit integer.

A single integer $N$.

A single integer: the number of ways to cut the plank into four pieces that form a quadrilateral with positive area.

For $N = 6$, there are $10$ ways to cut the plank into four ordered 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)$, and $(3,1,1,1)$. Four of them — $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, and $(3,1,1,1)$ — cannot form a quadrilateral, because one side is as long as the other three combined. That leaves $6$ valid ways.

Four lengths form a quadrilateral with positive area if and only if the longest piece is strictly shorter than the sum of the other three.