Найти остаток от деления 6^394 на 29

Можно расписать решение, пожалуйста

(Как можно быстро вспомнить малую теорему Ферма.)
Делимость 2^p - 2 на некоторое (большое) простое p
получается при помощи биномиальной теоремы:
2^p = (1+1)^p = 1^p + [сумма целых, содержащих множитель p] + 1.
Из делимости 2^p - 2 на p выводится делимость 3^p - 3 на p, так как
3^p = (2+1)^p = 2^p + [сумма целых, содержащих множитель p] + 1,
и хорошо видно, что 3^p - 3 = (2^p - 2) + [...] делится на p.
Сделанное для 2 и 3 можно повторить для 4,5,6,7,etc.,p-1.
Таким образом a^p - a, равное a*[a^(p-1)-1] , делится на p.
Но делимости а на р нет, - потому a^(p-1)-1 делится на р.