modulo

typedef long long int lli ;

long long int modular_inv(long long int a, long long int N ) ;


class stoper
{public:
    chrono::time_point<chrono::high_resolution_clock> a,b;
    void start(){a = chrono::high_resolution_clock::now();}
    void stop() {b = chrono::high_resolution_clock::now();}
    double val()
    {
        chrono::duration<double> elapsed_seconds = b-a;
        return elapsed_seconds.count();
    }
    void show()
    {
        chrono::duration<double> elapsed_seconds = b-a;
        cout << elapsed_seconds.count()<<"s ";
    }
};


int ile_dzielnikow(int x)
{

    int licznik=1;
    for (int i=2;i<=x;i++)
    {
        int w=0;
        while (x%i==0)
        {
            x=x/i;
            w++;
        }
        licznik*=(1+w);
    }
    if (x>1) licznik*=2;
    return licznik;
}




class dynmodulo
{public:
    unsigned int value;
    unsigned int n;
    dynmodulo(unsigned long long int x, int nn){ n=nn;value = x%n;}
    dynmodulo(long long int x, int nn){n=nn; if (x>0)       value = x%n;    else        value = n-(-x%n); }
    dynmodulo(int  x, int nn){n=nn; if (x>0)        value = x%n;    else        value = n-(-x%n); }
    dynmodulo(unsigned int  x, int nn){n=nn; value = x%n;}
    dynmodulo(){ value = 0;n=0;}
    dynmodulo operator + (dynmodulo a) { return dynmodulo(value+a.value,n); }
    dynmodulo operator - (dynmodulo a) { return dynmodulo(value-a.value,n); }
    dynmodulo operator * (dynmodulo a) { return dynmodulo(value*(unsigned long long int) a.value,n); }
    friend std::ostream& operator<< (std::ostream& stream, const dynmodulo a) { return stream<<a.value<<" (mod"<<a.n<<")"; }
    friend std::istream & operator>> (std::istream & stream,  dynmodulo &a) { int t; stream>>t; a=dynmodulo(t,a.n);   return stream; }
    dynmodulo inv() { return dynmodulo(modular_inv(value,n),n) ; }
    dynmodulo operator / (dynmodulo a) { return (*this)*a.inv(); }
};

template < int n>
class modulo
{public:
    unsigned int value;
    modulo(unsigned long long int x){ value = x%n;}
    modulo(long long int x){ if (x>=0)      value = x%n;    else        value = n-(-x%n); }
    modulo(int  x){ if (x>=0)       value = x%n;    else        value = n-(-x%n); }
    modulo(unsigned int  x){ value = x%n;}
    modulo(){ value = 0;}
    modulo operator + (modulo a) { return modulo(value+a.value); }
    modulo operator - (modulo a) { return modulo(value-a.value); }
    modulo operator * (modulo a) { return modulo(value*(unsigned long long int) a.value); }
    bool operator == (const modulo &a) { return value==a.value; }
    template <class T>
    bool operator == (const T &a) { return a==value; }
    friend std::ostream& operator<< (std::ostream& stream, const modulo a) { return stream<<a.value<<" (mod"<<n<<")"; }
    friend std::istream & operator>> (std::istream & stream,  modulo &a) { int t; stream>>t; a=modulo(t);   return stream; }
    modulo inv() { return modulo(modular_inv(value,n)) ; }
    modulo operator / (modulo a) { return (*this)*a.inv(); }
};



template <class T>
T power(T a, int ex)
{
    T r; // for NRVO
    if (ex==0)
    {
        T r = 1;
        return r;
    }
    else
    {
        if (ex%2==1) return a*power(a,ex-1);
        else
        {
            T t=power(a,ex/2);
            return t*t;
        }
    }
}

template <class T>
inline T sqr(const T x )
{
    return x*x;
}

template <class T>
T modpower(T const a, const int ex,T const m)
{
    if (ex==0) return T(1);
    else
    {
        if (ex%2==1)
        {
            //T t=modpower(a,ex-1,m);
            /*if ((t<0)||(t>=m))
            {
                t++;t--;
            }*/

            //return (a*t)%m;
            return (a*modpower(a,ex-1,m))%m;
        }
        else
        {
            //T t=modpower(a,ex/2,m);
           // if ((t<0)||(t>=m))
           // {
           //     t++;t--;
           // }
            //return (t*t)%m;
            return sqr(modpower(a,ex/2,m))%m;
        }
    }
}


/*
template <class T>
inline T sqr(const T x ){
    return x*x;
}
template <class T>
T modpower(T const a, const int ex,T const m)
{
    if (ex==0) return T(1);
    else    {
        if (ex%2==1) {
            return (a*modpower(a,ex-1,m))%m;
        } else        {
            return sqr(modpower(a,ex/2,m))%m;
        }
    }
}
*/