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