注意到 $n \geq 2229283$ 时，输出都为 $0$。

然后 $n < 2229283$ 时用 $dp$ 进行计算，$n \geq 2229283$ 时直接输出 $0$。