// Class Zm: Residue ring modulo m
#ifndef ZM_H
#define ZM_H 1

#include <iostream>
#include <cmath>
#include <cassert>

// Greatest Common Divizor (Euclid's Algorithm)
int gcd(int m, int n);

// Extended Euclid's Algorithm
// Input: integer numbers m, n, one of them must be nonzero.
// Output: d = gcd(m, n) and integers u, v such that
//     d = u*m + v*n
void extEucl(
    int m, int n,
    int& d, int& u, int& v
);

// Fast Power Algorithm
int powermod(int a, int n, int m);

class ZmException {
private:
    const char *errorText;
public:
    ZmException(const char* reason = ""):
       errorText(reason)
    {}
    
    const char* what() { return errorText; }
};

class Zm {
private:
    int n;
    static int m;
public:
    static int mod() { return m; }
    static void setMod(int mmm) { m = abs(mmm); }
    // int k = Zm::mod();
    // Zm::setMod(7);

    Zm(int x = 0):
        n(x%m)
    {}
    
    operator int() const { return n; }
    
    int number() const { return n; }
    int& number() { return n; }

    void setNumber(int k) { n = k%m; }

    Zm& operator+=(const Zm& k) {
        n = (n + k)%m;
        return *this;
    }
    
    Zm& operator-=(const Zm& k) {
        n = (n - k)%m;
        return *this;
    }
    
    Zm& operator*=(const Zm& k) {
        n = (n * k)%m;
        return *this;
    }
    
    Zm inverse() const {    // y = x.inverse();
        int d, u, v;
        extEucl(n, m, d, u, v);
        assert(d == u*n + v*m);
        if (d != 1)
            throw ZmException("Element is not invertible modulo m");
        // 1 == u*n (mod m)
        return Zm(u);
    }
                
    Zm& operator/=(const Zm& k) {
        n *= k.inverse();
        return *this;
    }
        
    Zm power(int e) const {
        int p = powermod(n, e, m);
        return Zm(p);
    }
    
    bool operator==(const Zm& k) const {
        return ((n - k)%m == 0);
    }
    
    bool operator!=(const Zm& k) const {
        return !operator==(k);
    }

    int residue() const {
        int r = n%m;
        if (r < 0)
            r += m;
        return r;
    }
    
    int signedResidue() const {
        int r = n%m;
        int m2 = m/2;
        if (r < (-m2))
            r += m;
        else if (
            r > m2 || (m%2 == 0 && r == m2)
        )
            r -= m;
        return r;
    }
    
    bool operator<(const Zm& k) const {
        return (residue() < k.residue());
    }
    
    bool operator<=(const Zm& k) const {
        return (residue() <= k.residue());
    }
    
    bool operator>(const Zm& k) const {
        return !operator<=(k);
    }

    bool operator>=(const Zm& k) const {
        return !operator<(k);
    }
};

inline Zm operator+(const Zm& a, const Zm& b) {     
    Zm res = a;
    res += b;
    return res;
}
    
inline Zm operator-(const Zm& a, const Zm& b) {     
    Zm res = a;
    res -= b;
    return res;
}

inline Zm operator*(const Zm& a, const Zm& b) {     
    Zm res = a;
    res *= b;
    return res;
}

inline Zm operator/(const Zm& a, const Zm& b) {     
    Zm res = a;
    res /= b;
    return res;
}

inline std::ostream& operator<<(std::ostream& s, const Zm& x) {
    //... s << int(x);
    s << x.signedResidue();
    return s;
}

inline std::istream& operator>>(std::istream& s, Zm& x) {
    int k;
    s >> k;
    if (s.good())
        x.setNumber(k);
    return s;
}

#endif /* defined ZM_H */