CF922B.Magic Forest

Imp is in a magic forest, where xorangles grow (wut?)

A xorangle of order $n$ is such a non-degenerate triangle, that lengths of its sides are integers not exceeding $n$ , and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order $n$ to get out of the forest.

Formally, for a given integer $n$ you have to find the number of such triples $(a,b,c)$ , that:

• $1<=a<=b<=c<=n$ ;
• , where denotes the bitwise xor of integers $x$ and $y$ .
• $(a,b,c)$ form a non-degenerate (with strictly positive area) triangle.

The only line contains a single integer $n$ $(1<=n<=2500)$ .

Print the number of xorangles of order $n$ .

The only xorangle in the first sample is $(3,5,6)$ .