inline long long sqr(int x){return 1ll*x*x;}
long long qp(int a,int b,int p){return !b?1:sqr(qp(a,b>>1,p))%p*(b&1?a:1)%p;}