逆元（inv）

• 什么是逆元
  当求解公式：(a/b)%m时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法；
  设c是b的逆元，则有_bc=1(mod m);
  则(a/b)%m=(a/b)1%m=(a/b)bc%m=ac%m=ac(mod m);_
  即a/b的模等于a*b的逆元的模；

• 求逆元的方法
  费马小定理
  假如p是质数，且gcd(a,p)=1，那么a^(p-1)≡1（mod）p(即a的p-1次方除以p的余数恒等于1)
  所以:a*a^(p-2)≡1(mod)p 对于整数a，p，a关于p的逆元就是a^(p-2)
  复杂度：O(log n);

const int mod =1e9+7;
long long quickmi(long long a,long long b){
    if(b==0)return 0;
    long long ret=1;
    a%=mod;
    while(b){
        if(b&1)ret=(ret*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ret;
}
long long inv(long long a){
    return quickmi(a,mod-2);
}