Возведение в степень и деление по модулю вручную

Воспользуйся свойством
( a * b ) mod c = ( ( a mod c ) * ( b mod c ) ) mod c
Твой пример расписывать не буду - много писанины. Возьму более простой пример.
2^9 mod 5 = 512 mod 5 = 2 (легко проверить на калькуляторе или на листике)
Теперь, если пользоваться указанным свойством
2^9 mod 5 = ((2^3 mod 5)(2^3 mod 5)(2^3 mod 5)) mod 5 = (3*3*3) mod 5 = 27 mod 5= 2

Есть еще такая запись указанного свойства
( a ^ b ) mod c = ( ( a mod c ) ^ b ) mod c(оно равносильно предыдущему, только запись через степень) . Можешь понижать степень до тех пор, пока не найдешь результат.

Есть еще такой метод - больше подходит для написания программ для вычислительных машин.

a^25 mod m. Переводим 25 (показатель степени в двоичную систему)
25 (дес) = 11001 (двоич) =2^4 + 2^3 + 2^0
таким образом a^25 mod n = (a * a^24) mod n = (a * a^8 * a^16) mod n =
= (a * (( a^2) ^2) ^2 * ((( a^2 ) ^2 ) ^2 ) ^2 mod n =
= (((( a^2 * a ) ^2 ) ^2 ) ^2 * a) mod n
таким образом a^25 можно вычислить по формуле:
((((((( a^2 mod n ) * a ) mod n ) ^2 mod n ) ^2 mod n ) ^2 mod n ) ^2 mod n) * a * mod n

Удачи.