問題文

N×N マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j)(1≤i,j≤N) と表します。

各マスには整数が 1 つ書かれており、(i,j) には i×j が書かれています。

(1,1) から開始して、右または下のマスへの移動を繰り返すことで (N,N) まで移動する経路を良い経路と呼びます。このとき、良い経路のスコアを「通ったマスに書かれている数字の総和」と定義します。

良い経路のスコアとしてありうる最大の値を M とします。M 以下の整数であって、良い経路のスコアとして現れない最大の値を求めてください。

制約

• 2 \le N \le 1000
• 入力はすべて整数

部分点

この問題には部分点が設定されている。

• N \le 30 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

3

出力例 1

20

例として、上の図に示した経路について考えます。

• 赤色の経路のスコアは 1 + 2 + 3 + 6 + 9 = 21 です。
• 青色の経路のスコアは 1 + 2 + 4 + 6 + 9 = 22 です。

その他にも経路は考えられますが、N = 3 の場合 M = 22 です。そして、M 以下の整数であって、経路のスコアとして現れない最大の値は 20 です。

入力例 2

6

出力例 2

152

入力例 3

9

出力例 3

476