cdef class mint:
    """A machine-sized non-overflowing brain-dead integer class."""

    cdef unsigned int value

    def __new__(self, unsigned int value=0):
        self.value = value

    def __str__(self):
        cdef unsigned int v
        v = self.value
        if v == 0:
            return '0'
        s = ''
        while v > 0:
            s = chr(v % 10 + 48) + s
            v = v / 10
        return s

    def __repr__(self):
        return '%s (%d)' % (hex(self), self.value)

    def __hash__(self):
        return self.value

    def __richcmp__(self, other, int op):
        cdef unsigned int v1, v2
        cdef int r
        v1 = self
        v2 = other
        if op == 0:   r = v1 <  v2
        elif op == 1: r = v1 <= v2
        elif op == 2: r = v1 == v2
        elif op == 3: r = v1 != v2
        elif op == 4: r = v1 >  v2
        elif op == 5: r = v1 >= v2
        return r

    def __add__(unsigned int v1, unsigned int v2):
        return mint(v1 + v2)

    def __sub__(unsigned int v1, unsigned int v2):
        return mint(v1 - v2)

    def __mul__(unsigned int v1, unsigned int v2):
        return mint(v1 * v2)

    def __div__(unsigned int v1, unsigned int v2):
        if v2 == 0:
            raise ZeroDivisionError
        return mint(v1 / v2)

    def __mod__(unsigned int v1, unsigned int v2):
        if v2 == 0:
            raise ZeroDivisionError
        return mint(v1 % v2)

    def __pow__(a, b, mod):
        cdef unsigned int v1, v2, result
        if mod is not None:
            return (a ** b) % mod   # wrong result if mod is large
        v1 = a
        v2 = b
        result = 1
        while 1:
            if v2 & 1:
                result = result * v1
            v2 = v2 >> 1
            if v2 == 0:
                return result
            v1 = v1 * v1

    def __neg__(unsigned int v1):
        return mint(-v1)

    def __pos__(unsigned int v1):
        return mint(v1)

    def __abs__(unsigned int v1):
        return mint(v1)

    def __nonzero__(unsigned int v1):
        return v1 != 0

    def __invert__(unsigned int v1):
        return mint(~v1)

    def __lshift__(unsigned int v1, int v2):
        return mint(v1 << v2)

    def __rshift__(unsigned int v1, int v2):
        return mint(v1 >> v2)

    def __and__(unsigned int v1, unsigned int v2):
        return mint(v1 & v2)

    def __or__(unsigned int v1, unsigned int v2):
        return mint(v1 | v2)

    def __xor__(unsigned int v1, unsigned int v2):
        return mint(v1 ^ v2)

    def __int__(self):
        return self.value

    def __long__(self):
        cdef unsigned int maxint
        result = long(self.value)
        if result < 0:
            maxint = -1
            maxint = maxint >> 1
            result = ((result + maxint) + maxint) + 2
        return result

    def __oct__(self):
        cdef unsigned int v
        v = self.value
        s = ''
        while v > 0:
            s = chr(v & 7) + s
            v = v >> 3
        return '0' + s

    def __hex__(self):
        cdef unsigned int d
        cdef unsigned int v
        cdef unsigned int template
        v = self.value
        template = -1
        s = ''
        while template > 0:
            d = v & 15
            if d < 10:
                d = d + 48
            else:
                d = d + 87
            s = chr(d) + s
            v = v >> 4
            template = template >> 4
        return '0x' + s