Here is another way. Remember that when we find `modulo multiplicative inverse`

of `a`

under mod `m`

.
Then

**a** and **m** must be `coprime`

with each other.

We can use `gcd extended`

for calculating `modulo multiplicative inverse`

.

For computing **a**^{b} *mod* m when `a`

and `b`

can have more than 10^{5} digits then its tricky to compute the result.

Below code will do the computing part :

```
#include <iostream>
#include <string>
using namespace std;
/*
* May this code live long.
*/
long pow(string,string,long long);
long pow(long long ,long long ,long long);
int main() {
string _num,_pow;
long long _mod;
cin>>_num>>_pow>>_mod;
//cout<<_num<<" "<<_pow<<" "<<_mod<<endl;
cout<<pow(_num,_pow,_mod)<<endl;
return 0;
}
long pow(string n,string p,long long mod){
long long num=0,_pow=0;
for(char c: n){
num=(num*10+c-48)%mod;
}
for(char c: p){
_pow=(_pow*10+c-48)%(mod-1);
}
return pow(num,_pow,mod);
}
long pow(long long a,long long p,long long mod){
long res=1;
if(a==0)return 0;
while(p>0){
if((p&1)==0){
p/=2;
a=(a*a)%mod;
}
else{
p--;
res=(res*a)%mod;
}
}
return res;
}
```

This code works because **a**^{b} *mod* m can be written as **(a ***mod* m)^{b mod m-1} *mod* m.

Hope it helped **{ :)**

`% 2`

insted of`% n`

in last`if`

`int`

overflows, but a 64-bit type would be enough. However, if you're seriously going for RSA, you need large integers,`gmp`

would be an option (and has modular power).7more comments