i have some knowldege of fermats little theorem but for that i think ‘b’ must be of the form : b=k*(p-1) + m…and the answer would be a^m…but in my case ‘b’ is smaller than p for example b is 10^7(so i cant express ‘b’ in terms of ‘p’) …??

By simply writing the expression it is overflowing the long long int range …plz help

you can use repeated squaring

it basically depends on the fact

you can use code:-

```
int mod = 1000000007
int powmod(int base,int pow)
{
int res=1;
while(pow)
{
if (pow%2!=0) res=(res*base)%mod;
base=(base*base)%mod;
pow/=2;
}
return res;
}
```

you can get more information from wiki-Exponentiation by squaring

2 Likes

```
MOD 1000000007
int expo(int base,int power)
{
int result=1;
while(power)
{
if(power&1)
result=(result*base)%MOD;
base=(base*base)%MOD;
power>>=1;
}
return result;
}
```

```
MOD 1000000007
int square(int a)
{
return (a*a)%MOD;
}
int expo(int base,int power)
{
if(power==1)
return base;
else if(power&1)
return (base*expo(base,power-1)) % MOD;
else
return square(expo(base,power/2))%MOD;
}
```

for large prime, replace int with long long

for large prime, replace int with long long