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

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

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

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