← 返回题目列表

Codeforces · 922/B

B. 魔法森林

中文机器翻译题面 查看原题

小鬼位于魔法森林中,那里生长着 xorangles(什么?)

n 阶异或角是一种非简并三角形,其边长为不超过 n 的整数,且长度的异或和等于 0。 Imp 必须计算 n 阶不同 xorangle 的数量才能离开森林。

形式上,对于给定的整数 n,您必须找到这样的三元组 (a, b, c) 的数量,即:

- 1 ≤ a ≤ b ≤ c ≤ n;
- $$a \oplus b \oplus c = 0$$,其中 $$x \oplus y$$ 表示整数 x 和 y 的按位异或。
- (a, b, c) 形成一个非退化(面积严格为正)三角形。

输入

唯一一行包含单个整数 n (1 ≤ n ≤ 2500)。

输出

打印 n 阶 xorangle 的数量。

示例

输入 #1

6

输出 #1

1

输入 #2

10

输出 #2

2

注意

第一个样本中唯一的异形是 (3, 5, 6)。