Найдите остаток от деления числа A, возведенного в факториал N, на P

Даны три целых числа A, N и P , задача состоит в том, чтобы найти (A^(N!)) % P.

Примеры:

Input: A = 2, N = 1, P = 2
Output: 0
Explanation: As (2^(1!)) = 2 
Therefore 2 % 2 will be 0.

Input: A = 3, N = 3, P = 2
Output: 1

Наивный подход: простейшим решением этой проблемы может быть нахождение факториала N скажем , f, а теперь вычислите A в степени fsay pow и найдите остаток от P.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N!)
Вспомогательное пространство: O(1)

Эффективный подход: вышеизложенное можно оптимизировать, используя концепцию модульного возведения в степень и некоторые свойства модуля и степени:

1. x^(a*b*c) can be written as :- (((x^a)^b)^c) …property of power. 
    
2. ((x^a)^b) % p can be written as :- ((x^a) %p)^b) % p …property of modulo.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: О(N*logN)
Вспомогательное пространство: O(1)