LL MOD(LL a, LL n, LL mod) {
  LL p=0;
  for(;n;) {
    if(n%2) {
      p+=a;
      if(p>=mod) p-=mod;
    }
    if(n/=2) {
      a+=a;
      if(a>=mod) a-=mod;
    }
  }
  return p;
}