Добрый день! Столкнулся с проблемой, что если нам нужно число a возвести в степень p, которая очень большая, то мы не можем брать показатель степень по данному нам простому модулю mod, это просто неправильно. В одной задаче мне нужно было вначале вычислить степень, в которую я буду возводить, а потом уже соответственно возводить, и на ограничениях, на которых показатель степени не нужно брать по модулю(он меньше 1е9 + 7) у меня AC, но на бОльших ограничениях, где уже нужно показатель степень брать по модулю у меня WA. Я подумал над малой теоремой Ферма и решил, что если брать показатель степени p по модулю (m — 1) то при дальнейшем возведение в степень ответ будет корректный, строгого доказательства у меня не было, но это вроде работало, но я получил WA(видимо раз модуль по которому мы берём уже не простой, то и неправильно). И я решил спросить: если какой-то способ считать показатель степень по данному нам простому модулю, а не записывать его длинной арифметикой?

Подскажите, пожалуйста, как работает предпосчёт факториалов с помощью которого считается кол-во размещений по модулю, встретился с этим на atcoder G25 и у многих одинаковый код(как на скриншоте), не понимаю что в нём происходит.

Есть другой вариант подсчёта invfactorial — с помощью быстрого возведения в степень(https://agc025.contest.atcoder.jp/submissions/2611599), но почему invfactorial[2] = fact[2] ^ (MOD — 2) тоже вообще не ясно.