该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小硬壳正在研究三角形。他认为周长是 $3$ 的倍数的三角形是“幸运三角形”。

现在给出一个正整数 $N$，请你从 $1$ 到 $N$（包含 $1$ 和 $N$）这 $N$ 个正整数中，挑选出三个数 $a, b, c$ 作为三角形的三条边。

要求必须满足以下三个条件：

• 构成三角形：任意两边之和大于第三边（$a + b > c$）。
• 不重复枚举：为了避免重复计算（例如 $(2,3,4)$ 和 $(4,3,2)$ 算同一种组合），规定三条边必须满足$$1 \le a \le b \le c \le N$$
• 幸运性质：三条边的和（即周长）必须能被 3 整除，即$$(a + b + c) \bmod 3 = 0$$

请编写程序，输出满足以上所有条件的三角形组合的个数。

输入格式

输入一个正整数 $N$。

输出格式

输出一个整数，表示幸运三角形的总数量。

5

9

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 100$。

数据范围较小，可使用 $O(N^3)$ 的方法求解。