RSA 암호화와 복호화

문제

서로 맞는 RSA 키의 $n$, $e$, $d$와 평문 $m$을 받는다. 암호문 $c = m^e \bmod n$과 복호화한 값 $c^d \bmod n$을 출력한다.

거듭제곱은 반복 제곱으로 계산한다. 지수의 마지막 비트가 1이면 현재 밑을 결과에 곱하고, 단계마다 밑을 제곱하고 지수를 오른쪽으로 한 칸 옮긴다. 곱할 때마다 $n$으로 나눈 나머지를 구한다. 나머지 두 개의 곱은 $10^{18}$보다 작으므로 unsigned long long에 담을 수 있다.

제한

$2 \le n \le 10^9$, $1 \le e, d \le 10^9$, . 은 서로 다른 두 소수의 곱이고 와 는 서로 맞는 지수이다.