問題文

素数 $p$ が与えられる。任意の自然数 $n$ について、

$f(n) = \displaystyle\sum_{k=1}^{p}k^n$ と定めたときの $f(n)$ $mod$ $p$ の最大値を求めよ。

制約

• $2 \leq p \leq 5 \times 10^3$
• $p$ は素数

入力

入力はすべて整数である。

p

出力

$f(n)$ $mod$ $p$ の最大値を一行に出力せよ。

サンプル

7

6

某大学の問題では $p=7$ としたときの問題です。例えば、$n=6$ を代入すると$f(n)$ $(mod$ $p)$の値は最大値6をとります。

11

10