i64 bigmod(i64 a,i64 b,i64 d) { i64 r=1; while(b) { if(b&1) r=(r*a)%d; b>>=1; a=(a*a)%d; } return r; }