123 : 素数の自乗で割った余り

$p_n$を$n$番目の素数とする. $(p_1 = 2, p_2 = 3, ...)$また$r$を$(p_n - 1)^n + (p_n + 1)^n$を${p_n}^2$で割った余りとする.

例えば$n = 3$のとき$p_3 = 5$であり$4^3 + 6^3 = 280 ≡ 5 \mod 25$である。

余り$r$が$10^9$より大きくなる$n$の最小値は$7037$である.

余り$r$が$10^{10}$より大きくなる最初の$n$を求めよ.