P2666 [USACO07OCT] Bessie's Secret Pasture S

Farmer John recently harvested an almost infinite number of sod patches and stacked them in an open area. These patches are all squares with nonnegative integer side lengths (including $0$). One day his cow Bessie discovered these delicious sod patches and wants to plant them in her secret pasture. She divides the sod into $1\times1$ unit pieces to place them into the $N$ cells of her pasture. Bessie is interested in how many different ways there are if she chooses four patches. If $N=4$, then she has $5$ different ways: (1,1,1,1), (2,0,0,0), (0,2,0,0), (0,0,2,0), (0,0,0,2); the numbers in parentheses denote side lengths. Note that order matters; for example, (1,2,3,4) and (4,3,2,1) are two different ways.

A single line with one integer $N$.

A single line containing one integer: the total number of ways.

Constraints: For 100% of the testdata, $1\le N\le10000$. Translated by ChatGPT 5