题目背景

玩过井字棋游戏吗？它的英文名字叫做 tic-tac-toe，是一个古老的博弈游戏。游戏在一个 $3 \times 3$ 的棋盘上进行。游戏约定，先在同一条线（横线、纵线或斜线）上占有 $3$ 枚棋子者得胜。尽管现在借助计算机可以生成这个游戏所有可能的情况，但这个古老的游戏从未失去它在博弈游戏中的意义。在它的身上不断可以看到有新的东西产生。比如，有人将井字棋游戏从平面空间扩展到三维空间，发明了立体井字棋。

立体井字棋的棋盘是一个 $n \times n \times n$ 的立方体，游戏双方在立方体的这 $n^3$ 个格子中布子。与传统井字棋游戏的规则相似，首先占据了一条线上的全部 $n$ 个格子的人获胜。

当然，这个立方体的大小是有考究的，并不是所有的正整数 $n$ 都合适：$n$ 小了获胜太易，先行者必胜；$n$ 大了获胜又太难，最后可能双方都无法获胜。为此，我们需要收集与该游戏有关的一些数据，以决定最佳的 $n$ 的值。我们想知道，对于某个 $n$，在游戏中有多少种获胜的情况。

你的任务是：确定在 $n \times n \times n$ 的立方体中放 $n$ 个子，有多少种布子方案可以使这 $n$ 个子连成一条线。

简化题意

在一个 $n^3$ 的正方体中放 $n$ 个子，有多少种情况可以使 $n$ 个子连成一条线。

输入格式

输入数据为一个正整数 $n$，表示立方体的大小。

输出格式

输出为一个正整数，它表示在 $n^3$ 的立方体中 $n$ 个格子连成一条直线的方案数。

2

28

样例解释

对于一个 $2\times 2\times 2$ 的正方体，任意选择一个格子后，无论选择任意一个其他 $7$ 个格子都可以构成对角线。所以方案总数为 $\frac{8\times 7}{2} = 28$。

数据规模

对于 $30\%$ 的数据，$n \le 10$；

对于 $100\%$ 的数据，$n \le 1000$。

update on 2023/1/9 by Lotuses

多加入 $50\%$ 的数据，$n \le 10^9$。（前面 $100\%$ 算 $50\%$）