题目内容

地面光伏电站在做容量预测时，需要从标称容量集合 $\{1,2,\ldots,n\}$ 中选出三个子阵容量 $x$、$y$、$z$，组成一个容量三元组。只有同时满足下列验收条件的三元组会计入预测方案数：

1. 容量非降：$1 \le x \le y \le z \le n$。
2. 三者按位异或结果为 $0$（对应二进制位相同得 $0$、不同得 $1$）。例如 $4\ (100_2)$ 与 $5\ (101_2)$ 满足 $4 \oplus 5 = 1\ (001_2)$。验收式为

3. 三边可构成三角形，即

由 $x \le y \le z$，后两个不等式自动成立，只需 $x+y>z$。

请统计合法容量三元组的个数。

输入描述

首先一行读入一个整型 $n$（$1 \le n \le 3000$）。

输出描述

写出一个非负整型，表示合法容量三元组的个数。

样例1

输入

4

输出

0

说明

在 $1$ 到 $4$ 中，$(1,2,3)$ 满足 $1 \le 1 \le 2 \le 3 \le 4$ 且 $1 \oplus 2 \oplus 3 = 0$，但 $1+2=3$ 并不大于 $3$，不能构成三角形。其余三元组均不满足异或为 $0$。故答案为 $0$。

样例2

输入

12

输出

5

说明

合法三元组共 $5$ 个：$(3,5,6)$、$(3,9,10)$、$(5,9,12)$、$(6,10,12)$、$(7,11,12)$。例如 $7 \oplus 11 = 12$，且 $7+11>12$；而 $(1,2,3)$ 虽异或为 $0$，但不满足三角形条件，不计入。