Inverze

#define MOD (1000000007)
ll gcdE(ll a,ll m,ll &x,ll &y){
    if(!a)return x=0,y=1,m;
    ll u,v,g(gcdE(m%a,a,u,v));
    return x=v-(m/a)*u,y=u,g;
}
ll inv(ll a,ll m=MOD){
    ll x,y,g(gcdE(a,m,x,y));
    return g==1?(x%m+m)%m:-1;
}