 # Findingf (K^n)%m

I have used square method which gives O(log(n))

``````long long int cal(long n,long p){
long long int ans=0;
//printf("p=%ld\n",p);
if(p==0)
return 1;
if(p==1)
return n;
if(p%2==0){
ans=cal(n,p/2)%MOD;
return(((ans%MOD)*(ans%MOD))%MOD);
}
else{
ans=(cal(n,(p-1)/2)%MOD)%MOD ;
return ((n%MOD)*(((ans%MOD)*(ans%MOD))%MOD))%MOD;
}

}
//evaluating process trough a main function which I haven't written
let k=7 and n can very large<=100000
if(n%2==0)

res=cal(k,n)%MOD;
else
res=((k%MOD)*(cal(k,n-1))%MOD)%MOD;
``````

I want to whether know have I used it in a correct way.Because its is giving correct ans in my test cases.I my solution is failing somewhere plz help me out

Now, if it is (k * n) % m, then you can simply use (k * n) % m = (k % m * n % m) % m. On the other hand, if it is (k ^ n) % m, where k is raised to the power of n, refer to this : http://www.sanfoundry.com/cpp-program-implement-modular-exponentiation-algorithm/ for modular exponentiation.

Terima kasih dan salam kenal.