gcd逆元

//一个模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)