Имп попал в волшебный лес, где растут ксоругольники (што?)
Ксоругольником порядка n называется такой невырожденный треугольник, что длины его сторон — целые числа, не превосходящие n, а их xor-сумма равна нулю. Чтобы выбраться из волшебного леса, необходимо быстро уметь считать количество ксоругольников порядка n.
Более формально, по заданному числу n необходимо найти количество таких троек (a, b, c), что:
- 1 ≤ a ≤ b ≤ c ≤ n;
-
, где запись
обозначает побитовое исключающее ИЛИ чисел x и y. - (a, b, c) образуют невырожденный (т. е. со строго положительной площадью) треугольник.