N=9 のとき候補となる整数が 9×108 個あるため、愚直処理だと2秒以内に答えが出るかどうか怪しいです。
そこで、2秒以内で処理できるように候補の枝刈りを考えます。
X(X−1)≡0(mod10N) なので 10N を素因数分解して考えると「X や X−1 が 2N または 5N の倍数でなければならない」ということに気づけます。
59=1953125 なので 5N の倍数だけ調べるようにすれば、2秒以内に余裕を持って処理することが出来ます。
別解として N=9 程度なら事前に愚直に計算しておき解を埋め込むことでACすることも出来ます。
また、dfsなどの工夫をすると100桁くらいでも答えを得ることが出来ます。