B. Волшебный лес
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имп попал в волшебный лес, где растут ксоругольники (што?)

Ксоругольником порядка n называется такой невырожденный треугольник, что длины его сторон — целые числа, не превосходящие n, а их xor-сумма равна нулю. Чтобы выбраться из волшебного леса, необходимо быстро уметь считать количество ксоругольников порядка n.

Более формально, по заданному числу n необходимо найти количество таких троек (a, b, c), что:

  • 1 ≤ a ≤ b ≤ c ≤ n;
  • , где запись обозначает побитовое исключающее ИЛИ чисел x и y.
  • (a, b, c) образуют невырожденный (т. е. со строго положительной площадью) треугольник.
Входные данные

В единственной строке задано число n (1 ≤ n ≤ 2500).

Выходные данные

Выведите искомое количество ксоругольников порядка n.

Примеры
Входные данные
6
Выходные данные
1
Входные данные
10
Выходные данные
2
Примечание

В первом примере единственным подходящим ксоругольником является (3, 5, 6).