Since n^m can be very large (n,m <= 50), does one need BigInteger? I would not want to do it, since I've already started coding the whole thing in C++...

Never mind, yes -- one does need BigInteger. Had to recode the whole thing in Java to get Accepted. Excellent problem!