別解です．

\(n^n\equiv X\pmod{10^{9}}\iff n^n\equiv X\pmod{2^9} \land n^n\equiv X\pmod{5^9}\)

から，\(\bmod 2^9\) の問題と \(\bmod 5^9\) の問題に分離して考えることにします．

Euler の定理から，次が分かります．

• \(a\) が \(2\) の倍数でないとき，\(a^b \bmod 2^{9}\) は \(a\bmod 2^{9}\) と \(b\bmod 2^8\) だけから決まる．
• したがって \(n\) が\(2\) の倍数でないとき，\(n^n\bmod 2^{9}\) は \(n\bmod 2^{9}\) だけから決まる．
• \(a\) が \(5\) の倍数でないとき，\(a^b \bmod 5^{9}\) は \(a\bmod 5^{9}\) と \(b\bmod 4\cdot 5^8\) だけから決まる．
• したがって \(n\) が \(5\) の倍数でないとき，\(n^n\bmod 5^{9}\) は \(n\bmod (4\cdot 5^{9})\) だけから決まる．

したがって，\(2^9+4\cdot 5^9\) 通り程度の全通りの前計算を行えば，すべての \(X\) に対して \(n^n\equiv X\bmod 2^9\), \(n^n\equiv X\bmod 5^9\) の解をそれぞれ \(\bmod 2^9\), \(\bmod 4\cdot 5^9\) で列挙できます．

実際に計算してみると各 \(X\) に対して前者の解は 1 つ，後者の解は 4 つあることが分かり，あとはこれらの組み合わせに対して CRT で \(n\bmod 10^9\) を復元すれば本問題を解くことができます．

結局，問題を解くだけであれば，\(\bmod 2^9\) や \(\bmod 5^9\) の場合の解がある程度少ないだろうと予想したあと上の解法を実装すれば十分です．ただし解がちょうど 1 つ，4 つであることを全探索なしに証明しようと思えば，公式解説と似た \(\bmod p^k\) から \(\bmod p^{k+1}\) に持ち上げる種類の議論をやはり行うことになると思います．

• 解答例：https://atcoder.jp/contests/arc172/submissions/50286987