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 $ .

输入输出样例

输入样例 #1

6

输出样例 #1

1

输入样例 #2

10

输出样例 #2

2

说明

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