O trabalhador Farmer John quer uma cerca de quatro lados para as vacas. Corta uma tábua de comprimento inteiro $N$ ($4\le N\le2,500$) em três pontos, obtendo quatro comprimentos inteiros.

Os comprimentos podem ser quaisquer inteiros positivos, desde que formem quadrilátero. Quantas formas de cortar produzem uma cerca completa?

Notas

• As formas diferem se uma corta num ponto onde a outra não. Não elimine simetrias nem complicações semelhantes.
• Porém, a área deve ser maior que $0$.
• Alegre-se: a resposta cabe num inteiro de 32 bits com sinal.

Entrada

• Linha 1: inteiro $N$.

Saída

• Linha 1: inteiro, número de cortes em quatro peças que formem quadrilátero válido.

Exemplos

Entrada 1

6

Saída 1

6

Note

A tábua mede 6.

Há 10 formas de cortá-la em quatro peças: $(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)$. Mas estas quatro não formam quadrilátero: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.

Subtarefas

Pontos: 250.

Autor do problema: Jeffrey Wang, 2007