521

This is according to Mathematica. I can get the last digit from the cycle from 1->3->9->7->1... of multiplying by 3 each time, but I haven't figured out a pattern to get the 5 and 2 yet.

...

My previous answer was wrong, although it got the right answer. Here's the "fixed" result. I think this one should be good...

This relies on finding 3^12 first.

3^12 = 531441, which isn't too tough to do on a calculator, or even by hand if you're feeling like some long multiplication.

The next step is to decompose 123456 in terms of 12*(2^a+2^b+...). If you do this, you get:

123456=12*(2^13+2^11+2^5+2^4)

Next, you use the property that 3^(a+b+c+d)=3^a*3^b*3^c*3^d:

3^123456=3^[12*(2^13+2^11+2^5+2^4)]=3^(12*2^13)*3^(12*2^11)*3^(12*2^5)*3^(12*2^4).

3^(12*2^n)=3^(12*2*2*2*2*2...*2), which means to take 3^12 and square it n times. You can do this squaring by the earlier method of only retaining the last 3 digits:

3^12=...441

3^(12*2)=(...441)*(...441)=...481

3^(12*2^2)=(...481)*(...481)=...361

3^(12*2^3)=...321

**3^(12*2^4)=...041**

**3^(12*2^5)=...681**

3^(12*2^6)=...761

3^(12*2^7)=...121

3^(12*2^8)=...641

3^(12*2^9)=...881

3^(12*2^10)=...161

**3^(12*2^11)=...921**

3^(12*2^12)=...241

**3^(12*2^13)=...081**

So back to

3^123456=3^(12*2^13)*3^(12*2^11)*3^(12*2^5)*3^(12*2^4)

3^123456=(...041)*(...681)*(...921)*(...081)=...521