RT

__uint128_t brt;
inline int mod(int ans){
	brt=((__uint128_t)1<<64)/k;
	ans=ans-k*(brt*ans>>64);
    while(ans>=k) ans-=k;
    return ans;
}