# 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.

its is alos O(logn)
what is wrong with my code?

Where is it giving a wrong answer? Maybe it is because of the recursive calls. Try to give the link where it is not working.

i geeting negative value
http://www.codechef.com/viewsolution/6829397

Terima kasih dan salam kenal.