(a/b)%mod{费马小定理,逆元}

$a^{(p-1)}=1(modp)a^\{(p-1)\}=1\; (mod\; \backslash \; p)$ // $a^p=a(modp)a^p\; =\; a(mod\; \backslash \; p)$ {p为质数，a不是p的倍数}

有费马小定理得： b 的逆元: c = b^(mod-2) 即 (a/b) %mod = a*c%mod

long long int Division(long long int x,long long int y,long long int mod){ //(a/b)%mod(mod为质数)
	//if(y==0)return -1;
	x%=mod;y%=mod;
	long long int index=mod-2,card=y;
	long long int sum=1;
	while(index){
		if(index&1)sum=(sum*card)%mod;
		card=(card*card)%mod;
		index=(index>>1);
	} 
	return x*sum%mod;
}

https://blog.csdn.net/tobeyours/article/details/79619333