몫의 나머지

수학정수론

$\lfloor b^n/a\rfloor$를 소수 $p$로 나눈 나머지를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T\leq500)$

두 번째 줄부터 $T$개의 줄에 걸쳐 정수 $a, b, n$과 소수 $p$가 주어진다. $(1\leq n\leq10^{18}, 1\leq a<b<p\leq10^9+7)$

각 테스트 케이스마다 $\lfloor b^n/a\rfloor$를 소수 $p$로 나눈 나머지를 한 줄에 하나씩 출력한다.

2
3 5 2 11
2 3 5 7

8
2

$\lfloor5^2/3\rfloor\equiv8\pmod{11}$

$\lfloor3^5/2\rfloor\equiv2\pmod{7}$