//一个模n的剩余类环中非零元[a]有逆元的充要条件为gcd(a,n)=1 //也就是说,如果gcd(a,mod)!=1,那么a对mod就没有逆元 //逆元表 //预处理O(n)查询O(1) const int maxn=1e7; const int mod=1e9+7; ll inv[maxn]; void inv_ini() { inv[1] = inv[0] = 1; for (ll i = 2; i < maxn; i++) inv[i] = (mod - mod / i)*inv[mod%i] % mod; } //a对mod的逆元为qpow(a,mod-2,mod) //欧几里得算法没用(a,mod-2,mod)