Magic Forest

1000ms

262144K

Description:

Imp is in a magic forest, where xorangles grow (wut?)

$\text{[math]}$

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;
$\text{[math]}$ , where $\text{[math]}$ denotes the bitwise xor of integers x and y.
(a, b, c) form a non-degenerate (with strictly positive area) triangle.

Input:

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

Output:

Print the number of xorangles of order n.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF922B