Farmer John a découpé dans le pâturage un nombre presque illimité de carrés de gazon de toutes les longueurs de côté entières. Parfois FJ engage mal la lame et crée même des carrés de côté 0. Il les empile soigneusement ; Bessie les remarque un après-midi.

Bessie souhaite toujours de l'herbe délicieuse dans son pâturage secret. Elle décide d'emporter exactement quatre carrés et de les découper en morceaux $1\times1$ pour couvrir les $N$ carrés unitaires du pâturage ($1 \le N \le 10,000$).

Combien de façons de choisir quatre carrés pour le couvrir ? Pour une taille 4, il y en a cinq : $(1,1,1,1)$, $(2,0,0,0)$, $(0,2,0,0)$, $(0,0,2,0)$, $(0,0,0,2)$. L'ordre compte : $(4,3,2,1)$ et $(1,2,3,4)$ sont différents.

Entrée

• Ligne 1 : un entier $N$.

Sortie

• Ligne 1 : un entier, le nombre de façons pour Bessie de choisir quatre carrés de gazon pour son pâturage.

Exemples

Entrée 1

4

Sortie 1

5

Auteur du problème : Jeffrey Wang, 2007