Eccoci.

Let $f(n)$ be the largest positive integer $x$ less than $10^9$ such that the last $9$ digits of $n^x$ form the number $x$ (including leading zeros), or zero if no such integer exists.

For example:

• $f(4) = 411728896$ ($4^{411728896} = \cdots 490\underline{411728896}$)
• $f(10) = 0$
• $f(157) = 743757$ ($157^{743757} = \cdots 567\underline{000743757}$)
• $\sum_{2 \le n \le 10^3} f(n) = 442530011399$

Find $\sum_{2 \le n \le 10^6}f(n)$.