## Powers With Trailing Digits

### Problem 455

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}= ...490__411728896__) - f(10) = 0
- f(157) = 743757 (157
^{743757}= ...567__000743757__) - Σf(n), 2 ≤ n ≤ 10
^{3}= 442530011399

Find Σf(n), 2 ≤ n ≤ 10^{6}.