Feb 29, a Unique day!

For a quicker computation, we can use the Binomial Theorem:

$29^{58} = (30 - 1)^{58} = \sum_{k=0}^{58} \binom{58}{k} 30^k (-1)^{58-k} = \sum_{k=0}^{58} \binom{58}{k} (-30)^k$

Notice that each term after $k = 5$ is a multiple of $30^6$ , and thus will not change the last 6 digits of the answer. Therefore we only need to worry about $0 \le k \le 5$ :

$k = 0 : \binom{58}{0} (-30)^0 = 1$ $k = 1 : \binom{58}{1} (-30)^1 = -1740$ $k = 2 : \binom{58}{2} (-30)^2 = \frac{58*57}{2} * 900 = 1487700$ $k = 3 : \binom{58}{3} (-30)^3 = \frac{58*57*56}{3*2*1} * (-27000) \equiv -112000 \pmod{1000000}$ $k = 4 : \binom{58}{4} (-30)^4 = \frac{58*57*56*55}{4*3*2*1} * 810000 \equiv 700000 \pmod{1000000}$ $k = 5 : \binom{58}{5} (-30)^5 = \frac{58*57*56*55*54}{5*4*3*2*1} * (-24300000) \equiv -800000 \pmod{1000000}$

Therefore, $29^{58} \equiv 1 - 1740 + 487700 - 112000 + 700000 - 800000 \equiv \boxed{273961} \pmod{1000000}$

run it to get to answer