Let r be the remainder when (a1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42: 6³ + 8³ = 728 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that r_max = 42.

For 3 a 1000, find r_max.