有一个 $N \times N$ 的网格。第 $i$ 行第 $j$ 列的格子用 $(i, j)$（$1 \le i, j \le N$）表示。

每个格子上写有一个整数，在 $(i, j)$ 格子上的数字为 $i \times j$。

我们称从 $(1,1)$ 开始，通过不断向右或向下移动到 $(N,N)$ 的路径为好路径。此时，好路径的分数定义为这条路径经过的所有格子上数字的总和。

记所有好路径分数的最大值为 $M$。请你求出不超过 $M$ 的整数中，作为任何好路径分数都不可能出现的最大的数是多少。

输入由标准输入按以下格式给出。

$N$

请输出答案。

部分分

本题有部分分。

• 若你能正确解决 $N \le 30$ 的数据集，则可以获得 1 分。

样例解释 1

比如，上图所示的路径：

• 红色路径的分数为 $1 + 2 + 3 + 6 + 9 = 21$。
• 蓝色路径的分数为 $1 + 2 + 4 + 6 + 9 = 22$。

除此以外还可以考虑其他路径。对于 $N=3$ 的情况，$M=22$。而不超过 $M$ 的整数中，作为任何路径分数都不可能出现的最大数是 $20$。

数据范围

• $2 \le N \le 1000$
• 输入均为整数。

由 ChatGPT 5 翻译