long long fast_exp(int base,long long exp,int mod)

{

    long long ans=1LL,a=base;

    while(exp!=)

    {

        if(exp&1LL) ans*=a,ans%=mod;

        a*=a,a%=mod;

        exp>>=;

    }

    return ans%mod;

}