__int128 qsm(__int128 a,__int128 b,__int128 p) { __int128 res=1; while(b) { if(b&1) res=res*a%p; b>>=1; a=a*a%p; } return res%p; }
