Floresta Mágica

Thiago está em uma floresta, onde xorângulos crescem. (?)

Um xorângulo de ordem $n$ é um triângulo não degenerado, tal que seus lados são interos não excedendo $n$, e a sum-xor dos seus lados é igual à zero. Thiago tem que contar o numero de xorângulos distintos de ordem $n$ para poder sair da floresta.

Formalmente, para um número $n$ você tem que achar o número de triplas $(a,b,c)$, tal que:

• $1 \leq a \leq b \leq c \leq n$
• $a \oplus b \oplus c = 0$, onde $\oplus$ denota o xor binário.
• $(a, b, c)$ formam um triângulo não degenerado (com área estritamente positiva).

Entrada

A entrada é composta de um uníco inteiro $n$.

Saída

A saída deve ser um uníco inteiro, o número de xorângulos de ordem $n$.

Restrições

• $1\leq n \leq 2500$

Exemplos