Magic Forest

### 题目大意 给定一个正整数$n$ ，求满足如下条件的三元组$(a,b,c)$ 的个数： - $1 \le a \le b \le c \le n$ - $a \space xor \space b \space xor \space c=0$ - 存在一个边长分别为$a,b,c$ 的三角形。 ### 输入格式 一行一个正整数$n(1 \le n \le 2500)$ ### 输出格式 输出满足题意的三元组个数。 感谢U3144 浮尘ii 提供的翻译

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](https://en.wikipedia.org/wiki/Bitwise_operation#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 $ .

6

1

10

2

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