Tam giác XOR

Cho một số nguyên dương $n$. Hãy đếm số bộ ba $(a,b,c)$ thỏa mãn đồng thời các điều kiện sau:

• $1\le a\le b\le c\le n$;
• $a\oplus b\oplus c=0$, trong đó $\oplus$ là phép XOR (hoặc loại trừ) trên các số nguyên;
• $(a,b,c)$ là độ dài ba cạnh của một tam giác không suy biến (tam giác có diện tích dương).

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

In ra một số nguyên là số bộ ba $(a,b,c)$ thỏa mãn.

Ràng buộc

• $1\le n\le 2500$.

Ví dụ