Background

虽然 这里 已经有了一道二维威佐夫的板子题，但这道题是三维威佐夫。

虽然那道题是紫题，但我觉得这道顶多 1600。

xixisuper 认为是 2000，所以他就是 2000 了。

Description

取石子游戏需要两名玩家和三堆石子。

每一名玩家在自己的回合可以从堆中取走一个或多个石子。然而，如果玩家从多个堆中取石子，从其中每个堆所取的石子数目必须一致。

也就是说，每一名玩家选择一个数 $N>0$，然后移走：

• 一个堆中的 $N$ 个石子；
• 两个堆中各 $N$ 个石子（共 $2N$ 个）；
• 三个堆中各 $N$ 个石子（共 $3N$ 个）。

拿走最后一枚石子的玩家赢得游戏。

定义必败态为无论先手玩家如何操作，后手玩家必胜的状态。特别地，认为 $(0,0,0)$ 是必败态。

例如，$(0,1,2)$ 和 $(1,3,3)$ 是必败态。

考虑所有 $0\le x_i\le y_i \le z_i \le N$ 的必败态，求 $\sum (x_i+y_i+z_i)$。

Constraints and Subtasks

• $N\le 1500$

另外，还有一些测试点满足特殊要求。

分值	特殊性质
$20\%$	$N\le 300$
$80\%$	无特殊性质

请注意本题的空间限制。

为了限制打表代码，设选手代码为 $n$ 字节，则若

1. $n\le 4\times 1024$，将得到满分；
2. 否则，设满分 $S$ 分，得到 $\left\lfloor\dfrac{S\times 4\times 1024}{n}\right\rfloor$ 分。

---

Input

输入内容从标准输入中给出，格式如下：

$\boxed{\begin{aligned} & N \end{aligned}}$

Output

输出一行，包含一个整数，表示问题的答案。

Sample

3

10

100

173895