RSA密码是一种常用的加密方式，其基本操作如下所示：

选择两个奇质数 $p$ 和 $q$，令 $n=pq$，算出 $\varphi(n)=(p-1)(q-1)$，选一个整数 $e$（$1\leq e<\varphi(n),\gcd(e,\varphi(n))=1$），再算出 $e$ 在模 $\varphi(n)$ 意义下的逆元 $d$（$de\equiv 1\pmod{\varphi(n)}$）。这样，我们就有了一个明钥 $(n,e)$，和一个秘钥 $(n,d)$。

如果想要发送一个整数 $m$ （明文）给另一方，我们会算出 $c=m^e \bmod n$，就是密文。发送到另一方手中时，另一方会算出 $c^d \bmod n$。根据欧拉定理，这个结果等于原来的 $m$，即明文。如果 $n$ 很大而且不知道密钥，那么就很难知道明文。

输入 $n,e,c(15\leq n\leq10^9,1\leq e,c\leq n)$，求明文 $m$。多组数据，每组数据一行。（具体看样例）

Translated by 庄nnnn额

源代码：

RSA密码是一种常用的加密方式，其基本操作如下所示：

选择两个奇质数 $p$ 和 $q$，令 $n=pq$，算出 $\varphi(n)=(p-1)(q-1)$，选一个整数 $e$（$1\leq e<\varphi(n),\gcd(e,\varphi(n))=1$），再算出 $e$ 在模 $\varphi(n)$ 意义下的逆元 $d$（$de\equiv 1\pmod{\varphi(n)}$）。这样，我们就有了一个明钥 $(n,e)$，和一个秘钥 $(n,d)$。

如果想要发送一个整数 $m$ （明文）给另一方，我们会算出 $c=m^e \bmod n$，就是密文。发送到另一方手中时，另一方会算出 $c^d \bmod n$。根据欧拉定理，这个结果等于原来的 $m$，即明文。如果 $n$ 很大而且不知道密钥，那么就很难知道明文。

输入 $n,e,c(15\leq n\leq10^9,1\leq e,c\leq n)$，求明文 $m$。多组数据，每组数据一行。（具体看样例）

Translated by [庄nnnn额](https://www.luogu.com.cn/user/521592)