El trabajador Farmer John quiere una cerca de cuatro lados para las vacas. Corta una tabla de longitud entera $N$ ($4\le N\le2,500$) en tres puntos para obtener cuatro piezas de longitud entera.
Las longitudes pueden ser cualesquiera enteros positivos si forman un cuadrilátero. ¿Cuántas formas de cortar permiten una cerca completa?
Notas
- Las formas difieren si una corta en un punto donde la otra no. No elimines simetrías ni otras complicaciones similares.
- Pero el área debe ser mayor que $0$.
- Alégrate: la respuesta cabe en un entero con signo de 32 bits.
Entrada
- Línea 1: entero $N$.
Salida
- Línea 1: entero, número de cortes en cuatro piezas que formen un cuadrilátero válido.
Ejemplos
Entrada 1
6
Salida 1
6
Nota
La tabla mide 6.
Puede dividirla en cuatro piezas de 10 formas: $(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)$. Pero estas cuatro no forman cuadrilátero: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.
Subtareas
Puntos: 250.
Autor del problema: Jeffrey Wang, 2007