Can somebody help me with this?

I saw in a magazine that there was a contest or something about determining the 3 last digits of 3^123456, is there anyone that could help with this? 

$\small{ \begin{array}{rcll} 3^{123456} \pmod {1000} & \equiv & ? \\ \end{array} }$

$\boxed{~ \small{ \begin{array}{rcll} a^{\varphi{(m)}} &= 1 \pmod {m}, \qquad \text{ if } gcd(a,m) = 1 \end{array} } ~}$

$\small{a = 3}$

$\small{m = 1000 = 2^3 \cdot 5^3}$

1.)  $\small{ gcd(3,1000) = 1 }$

2.)

 $\small{ \begin{array}{rcll} \varphi{(1000)} &=& 1000 \cdot \left( 1-\frac{1}{2} \right)\cdot \left( 1-\frac{1}{5} \right) \\ \varphi{(1000)} &=& 1000 \cdot \left( \frac12 \right)\cdot \left( \frac{4}{5} \right) \\ \varphi{(1000)} &=& 400 \\ \end{array} }$

3.)  $\small{ \begin{array}{rcll} 3^{400} &= 1 \pmod {1000} \\ \end{array} }$

4. Split 123456 in units of 400

$\small{ \begin{array}{rcll} 123456 &=& 400 \cdot 308 + 256 \\ 3^{123456} \pmod {1000} &=& 3^{400 \cdot 308 + 256} \pmod {1000} \\ &=& 3^{400 \cdot 308} \cdot 3^{256} \pmod {1000} \\ &=& ( \underbrace{3^{400}}_{=1\pmod {1000} } )^{308} \cdot 3^{256} \pmod {1000} \\ &=& 1^{308} \cdot 3^{256} \pmod {1000} \\ &=& 1 \cdot 3^{256} \pmod {1000} \\ &=& 3^{256} \pmod {1000} \qquad | \qquad 3^{10} = 49 \pmod {1000}\\ &=& 3^{10\cdot 25+6} \pmod {1000}\\ &=& 3^{10\cdot 25} \cdot 3^6 \pmod {1000}\\ &=& (3^{10})^{25} \cdot 3^6 \pmod {1000}\\ &=& (49)^{25} \cdot 3^6 \pmod {1000}\\ \end{array} }$

$\small{ = 1311081016089963454886184368275274375604160521\pmod {1000}\\ = 521 }$

Here are the last 10 digits =7044619521