When the dividend is some huge power but the modulus is not so big, I can use modular exponentiation. But how can I compute the residue when the modulus is, for example, $2^{107} - 1$, a Mersenne prime, as in $$8934^{3167} \bmod{(2^{107} -1)}$$
Thank you.
Such calculations occur routinely in cryptography with moduli ten times as long (or more) as your 107 bits.
They are out of reach of realistic pencil-and-paper calculations, of course, but can be done without too much trouble on a computer with the straightforward implementations of algorithms (such as exponentiation-by-squaring) that work by hand in smaller cases.
In applications where efficiency is important, some extra performance can be squeezed out using tricks such as Montgomery reduction and efficient multiplication algorithms.