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.

Imp 来到了一片魔法森林，这里生长着“异或三角形”（啥？）

一个阶数为 $n$ 的异或三角形，是指一个非退化的三角形，其三边长度均为不超过 $n$ 的正整数，且三边长度的异或和等于零。Imp 必须计算出阶数为 $n$ 的不同异或三角形的数目，才能走出这片森林。

形式化地，对于给定的正整数 $n$，你需要找出满足以下条件的三元组 $(a,\,b,\,c)$ 的个数：

• $1 \le a \le b \le c \le n$；
• $a \oplus b \oplus c = 0$，其中 $x \oplus y$ 表示整数 $x$ 与 $y$ 的按位异或运算；
• $(a,\,b,\,c)$ 构成一个非退化三角形（即具有严格正的面积）。

The only line contains a single integer n (1 ≤ n ≤ 2500).

唯一一行包含一个整数 $n$（$1 \leq n \leq 2500$）。

Print the number of xorangles of order n.

输出阶数为 $n$ 的 xorangle 的数量。

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

第一个样例中唯一的 xorangle 是 (3, 5, 6)。