TypeError: unsupported operand type(s) for ** or pow()

[Mekire]

This isn't your issue, but for general knowledge here the python builtin pow actually takes a third argument to mod by to take advantage of modular exponentiation.

So like pow(456, 89700, 17) instead of (456**89700) % 17.

Interestingly enough though the interpreter does seem smart enough to use modular exponentiation in the second case as well but I'm not sure if this is part of spec or just an implementation detail you can't rely on.  If you tried to do the exponentiation in one expression and then the mod in another though your program could take eons.

Edit: Actually on second thought I think the second version is done inefficiently. The first version should always be much faster.