mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので(最適かは知らんが)pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな