The usual trick is repeated squaring. If you want to raise a number $x$ to the 59th power, you follow this algorithm:
x1 = x x2 = x1 * x1 x4 = x2 * x2 x8 = x4 * x4 x16 = x8 * x8 x32 = x16 * x16 x59 = x32 * x16 * x8 * x2 * x1
Usually the algorithm is given using the following recurrence equations: $ x^{2n} = (x^n)^2, x^{2n+1} = (x^n)^2\cdot x. $ Using these equations, you can write a function that raises a number to a power.
Since you're computing everything modulo $n$, don't forget to reduce modulo $n$ each time. This will keep the numbers small and so the effort manageable.