Magic Forest

Imp는 xor각이 자라는 마법의 숲에 있다(뭐라고?).

차수가 n인 xor각은 변의 길이가 n을 넘지 않는 정수이고, 그 길이들의 xor 합이 영인 비퇴화 삼각형이다. Imp는 숲에서 빠져나가기 위해 차수가 n인 서로 다른 xor각의 개수를 세어야 한다.

형식적으로, 주어진 정수 n에 대해 다음 조건을 만족하는 삼중항 (a, b, c)의 개수를 구해야 한다.

• 1 ≤ a ≤ b ≤ c ≤ n;
• . 여기서 는 정수 x와 y의 비트별 xor을 나타낸다.
• (a, b, c)는 비퇴화(넓이가 엄격히 양수인) 삼각형을 이룬다.

유일한 줄에 하나의 정수 n (1 ≤ n ≤ 2500)이 주어진다.

차수가 n인 xor각의 개수를 출력한다.

첫 번째 예제의 유일한 xor각은 (3, 5, 6)이다.