Intermediário Infomática - Semana 34

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

Entrada Saída
6 1
10 2