#include
//#include

using namespace std;

typedef long long LL;

LL A,B,C;

LL recur(LL b){
//cout<<b<<endl;
if(b==1) return A%C;
LL t1 = recur(b/2);
t1 = (t1*t1)%C;
if(b%2==1) t1 = (t1*A)%C;
return t1;
}

/*LL pow(LL X,int p){
LL ret = 1;
for(int i=0;i<p;++i) ret=(ret*X)%C;
return ret;
}

LL recur10(LL b){
if(b<10) return pow(A,b);
LL t1 = recur10(b/10);
t1 = pow(t1,10);
for(int i=0;i> T;