# Use complement negation for mixed sign addition. (6)
# @see GA5Sy6
 
import itertools
import operator
import random
 
class Num:
    base = 2**8
 
    def __init__(self, init=0):
        if isinstance(init, tuple):
            self.m = init[0].copy()
            self.s = init[1]
        else:
            self.m = iton(abs(init), Num.base)
            self.s = init < 0
 
    def __neg__(self):
        return Num((self.m, not self.s))
 
    def __add__(self, other):
        return Num(nadd(self.m, self.s, other.m, other.s, Num.base))
 
    def __sub__(self, other):
        t = _fixsign(other.m, not other.s)[1]
        return Num(nadd(self.m, self.s, other.m, t, Num.base))
 
    def __mul__(self, other):
        return Num(nmul(self.m, self.s, other.m, other.s, Num.base))
 
    def __str__(self):
        return '-' * self.s + ntos(self.m, Num.base)
 
    def __repr__(self):
        return str((self.m, self.s))
 
# Utility.
 
def _iszero(a):
    return len(a) == 1 and a[0] == 0
 
def _fixsign(a, s):
    return a, s and not _iszero(a)
 
def _zeroextend(a, n):
    return a[:] + [0] * (n - len(a))
 
def _zeroreduce(a):
    n = len(a)
    while n != 1 and a[n-1] == 0:
        n -= 1
    return a[:n]
 
def _inplace_addc(r, a, c, b):
    for i in range(len(r)):
        c, r[i] = divmod(r[i] + a[i] + c, b)
    return c, r
 
def _inplace_mulc(r, x, c, b):
    for i in range(len(r)):
        c, r[i] = divmod(r[i] * x + c, b)
    return c, r
 
def _complement(a, b):
    return [b-1-x for x in a]
 
def _negate(a, b):
    return _inplace_addc(_complement(a, b), _zeroextend([1], len(a)), 0, b)[1]
 
# Convert.
 
def iton(x, b):
    r = []
    while True:
        x, y = divmod(x, b)
        r.append(y)
        if x == 0:
            return r
 
def nton(a, bi, bo):
    r = [0]
    for x in reversed(a):
        c = _inplace_mulc(r, bi, x, bo)[0]
        if c != 0:
            r.extend(iton(c, bo))
    return r
 
def ntos(a, b):
    return ''.join(map(str, reversed(nton(a, b, 10))))
 
# Compare.
 
def _cmp(x, y):
    if x != y:
        return -1 if x < y else 1
    return 0
 
def ncmp(a, b):
    n = len(a)
    m = len(b)
    u = itertools.chain([n], reversed(a))
    v = itertools.chain([m], reversed(b))
    return next(itertools.dropwhile(lambda x: x == 0, map(_cmp, u, v)), 0)
 
# Shift.
 
def nshl(a, n):
    return _zeroreduce([0] * n + a[:])
 
def nshr(a, n):
    return _zeroextend(a[n:], 1)
 
# Add.
 
def _add(a, b, base):
    n = 1 + max(len(a), len(b))
    a = _zeroextend(a, n)
    b = _zeroextend(b, n)
    return _zeroreduce(_inplace_addc(a, b, 0, base)[1])
 
def nadd(a, s, b, t, base):
    if s == t:
        return _fixsign(_add(a, b, base), s)
    if s:
        a, b = b, a
    a = _zeroextend(a, len(b))
    b = _zeroextend(b, len(a))
    c, r = _inplace_addc(a, _negate(b, base), 0, base)
    if not c:
        r = _negate(r, base)
    return _fixsign(_zeroreduce(r), not c)
 
# Multiply.
 
def _mul1(a, x, base):
    n = 1 + len(a)
    return _zeroreduce(_inplace_mulc(_zeroextend(a, n), x, 0, base)[1])
 
def _mul(a, b, base):
    if _iszero(b):
        return [0]
    return _add(_mul1(a, b[0], base), _mul(nshl(a, 1), nshr(b, 1), base),
                base)
 
def nmul(a, s, b, t, base):
    return _fixsign(_mul(a, b, base), s != t)
 
# Test.
 
def _test(n, op):
    w = Num.base
    z = (0, 1, -1, w, -w, w-1, 1-w)
    for x, y in itertools.product(z, repeat=2):
        u = int(str(op(Num(x), Num(y))))
        v = op(x, y)
        assert u == v, f'{op}({x}, {y})\nExpected:{v}, Got:{u}'
    w = Num.base ** 3
    for _ in range(n):
        x = random.randint(-w, w)
        y = random.randint(-w, w)
        u = int(str(op(Num(x), Num(y))))
        v = op(x, y)
        assert u == v, f'{op}({x}, {y})\nExpected:{v}, Got:{u}'
 
n = 1000
_test(n, operator.add)
_test(n, operator.sub)
_test(n, operator.mul)
 
def show1(a):
    print(repr(a), a, sep='; ')
 
def _show(z, op):
    print(op)
    for x, y in itertools.product(z, repeat=2):
        show1(op(Num(x), Num(y)))
 
w = Num.base
z = (0, 1, -1, w, -w)
_show(z, operator.add)
_show(z, operator.sub)
_show(z, operator.mul)
 
def factorial(n):
    r = Num(1)
    for i in range(2, n+1):
        r *= Num(i)
    return r
 
print(factorial)
for i in range(5):
    show1(factorial(10*i))

IyBVc2UgY29tcGxlbWVudCBuZWdhdGlvbiBmb3IgbWl4ZWQgc2lnbiBhZGRpdGlvbi4gKDYpCiMgQHNlZSBHQTVTeTYKCmltcG9ydCBpdGVydG9vbHMKaW1wb3J0IG9wZXJhdG9yCmltcG9ydCByYW5kb20KCmNsYXNzIE51bToKICAgIGJhc2UgPSAyKio4CgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGluaXQ9MCk6CiAgICAgICAgaWYgaXNpbnN0YW5jZShpbml0LCB0dXBsZSk6CiAgICAgICAgICAgIHNlbGYubSA9IGluaXRbMF0uY29weSgpCiAgICAgICAgICAgIHNlbGYucyA9IGluaXRbMV0KICAgICAgICBlbHNlOgogICAgICAgICAgICBzZWxmLm0gPSBpdG9uKGFicyhpbml0KSwgTnVtLmJhc2UpCiAgICAgICAgICAgIHNlbGYucyA9IGluaXQgPCAwCgogICAgZGVmIF9fbmVnX18oc2VsZik6CiAgICAgICAgcmV0dXJuIE51bSgoc2VsZi5tLCBub3Qgc2VsZi5zKSkKCiAgICBkZWYgX19hZGRfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIE51bShuYWRkKHNlbGYubSwgc2VsZi5zLCBvdGhlci5tLCBvdGhlci5zLCBOdW0uYmFzZSkpCgogICAgZGVmIF9fc3ViX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHQgPSBfZml4c2lnbihvdGhlci5tLCBub3Qgb3RoZXIucylbMV0KICAgICAgICByZXR1cm4gTnVtKG5hZGQoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIHQsIE51bS5iYXNlKSkKCiAgICBkZWYgX19tdWxfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIE51bShubXVsKHNlbGYubSwgc2VsZi5zLCBvdGhlci5tLCBvdGhlci5zLCBOdW0uYmFzZSkpCgogICAgZGVmIF9fc3RyX18oc2VsZik6CiAgICAgICAgcmV0dXJuICctJyAqIHNlbGYucyArIG50b3Moc2VsZi5tLCBOdW0uYmFzZSkKCiAgICBkZWYgX19yZXByX18oc2VsZik6CiAgICAgICAgcmV0dXJuIHN0cigoc2VsZi5tLCBzZWxmLnMpKQoKIyBVdGlsaXR5LgoKZGVmIF9pc3plcm8oYSk6CiAgICByZXR1cm4gbGVuKGEpID09IDEgYW5kIGFbMF0gPT0gMAoKZGVmIF9maXhzaWduKGEsIHMpOgogICAgcmV0dXJuIGEsIHMgYW5kIG5vdCBfaXN6ZXJvKGEpCgpkZWYgX3plcm9leHRlbmQoYSwgbik6CiAgICByZXR1cm4gYVs6XSArIFswXSAqIChuIC0gbGVuKGEpKQoKZGVmIF96ZXJvcmVkdWNlKGEpOgogICAgbiA9IGxlbihhKQogICAgd2hpbGUgbiAhPSAxIGFuZCBhW24tMV0gPT0gMDoKICAgICAgICBuIC09IDEKICAgIHJldHVybiBhWzpuXQoKZGVmIF9pbnBsYWNlX2FkZGMociwgYSwgYywgYik6CiAgICBmb3IgaSBpbiByYW5nZShsZW4ocikpOgogICAgICAgIGMsIHJbaV0gPSBkaXZtb2QocltpXSArIGFbaV0gKyBjLCBiKQogICAgcmV0dXJuIGMsIHIKCmRlZiBfaW5wbGFjZV9tdWxjKHIsIHgsIGMsIGIpOgogICAgZm9yIGkgaW4gcmFuZ2UobGVuKHIpKToKICAgICAgICBjLCByW2ldID0gZGl2bW9kKHJbaV0gKiB4ICsgYywgYikKICAgIHJldHVybiBjLCByCgpkZWYgX2NvbXBsZW1lbnQoYSwgYik6CiAgICByZXR1cm4gW2ItMS14IGZvciB4IGluIGFdCgpkZWYgX25lZ2F0ZShhLCBiKToKICAgIHJldHVybiBfaW5wbGFjZV9hZGRjKF9jb21wbGVtZW50KGEsIGIpLCBfemVyb2V4dGVuZChbMV0sIGxlbihhKSksIDAsIGIpWzFdCgojIENvbnZlcnQuCgpkZWYgaXRvbih4LCBiKToKICAgIHIgPSBbXQogICAgd2hpbGUgVHJ1ZToKICAgICAgICB4LCB5ID0gZGl2bW9kKHgsIGIpCiAgICAgICAgci5hcHBlbmQoeSkKICAgICAgICBpZiB4ID09IDA6CiAgICAgICAgICAgIHJldHVybiByCgpkZWYgbnRvbihhLCBiaSwgYm8pOgogICAgciA9IFswXQogICAgZm9yIHggaW4gcmV2ZXJzZWQoYSk6CiAgICAgICAgYyA9IF9pbnBsYWNlX211bGMociwgYmksIHgsIGJvKVswXQogICAgICAgIGlmIGMgIT0gMDoKICAgICAgICAgICAgci5leHRlbmQoaXRvbihjLCBibykpCiAgICByZXR1cm4gcgoKZGVmIG50b3MoYSwgYik6CiAgICByZXR1cm4gJycuam9pbihtYXAoc3RyLCByZXZlcnNlZChudG9uKGEsIGIsIDEwKSkpKQoKIyBDb21wYXJlLgoKZGVmIF9jbXAoeCwgeSk6CiAgICBpZiB4ICE9IHk6CiAgICAgICAgcmV0dXJuIC0xIGlmIHggPCB5IGVsc2UgMQogICAgcmV0dXJuIDAKCmRlZiBuY21wKGEsIGIpOgogICAgbiA9IGxlbihhKQogICAgbSA9IGxlbihiKQogICAgdSA9IGl0ZXJ0b29scy5jaGFpbihbbl0sIHJldmVyc2VkKGEpKQogICAgdiA9IGl0ZXJ0b29scy5jaGFpbihbbV0sIHJldmVyc2VkKGIpKQogICAgcmV0dXJuIG5leHQoaXRlcnRvb2xzLmRyb3B3aGlsZShsYW1iZGEgeDogeCA9PSAwLCBtYXAoX2NtcCwgdSwgdikpLCAwKQoKIyBTaGlmdC4KCmRlZiBuc2hsKGEsIG4pOgogICAgcmV0dXJuIF96ZXJvcmVkdWNlKFswXSAqIG4gKyBhWzpdKQoKZGVmIG5zaHIoYSwgbik6CiAgICByZXR1cm4gX3plcm9leHRlbmQoYVtuOl0sIDEpCgojIEFkZC4KCmRlZiBfYWRkKGEsIGIsIGJhc2UpOgogICAgbiA9IDEgKyBtYXgobGVuKGEpLCBsZW4oYikpCiAgICBhID0gX3plcm9leHRlbmQoYSwgbikKICAgIGIgPSBfemVyb2V4dGVuZChiLCBuKQogICAgcmV0dXJuIF96ZXJvcmVkdWNlKF9pbnBsYWNlX2FkZGMoYSwgYiwgMCwgYmFzZSlbMV0pCgpkZWYgbmFkZChhLCBzLCBiLCB0LCBiYXNlKToKICAgIGlmIHMgPT0gdDoKICAgICAgICByZXR1cm4gX2ZpeHNpZ24oX2FkZChhLCBiLCBiYXNlKSwgcykKICAgIGlmIHM6CiAgICAgICAgYSwgYiA9IGIsIGEKICAgIGEgPSBfemVyb2V4dGVuZChhLCBsZW4oYikpCiAgICBiID0gX3plcm9leHRlbmQoYiwgbGVuKGEpKQogICAgYywgciA9IF9pbnBsYWNlX2FkZGMoYSwgX25lZ2F0ZShiLCBiYXNlKSwgMCwgYmFzZSkKICAgIGlmIG5vdCBjOgogICAgICAgIHIgPSBfbmVnYXRlKHIsIGJhc2UpCiAgICByZXR1cm4gX2ZpeHNpZ24oX3plcm9yZWR1Y2UociksIG5vdCBjKQoKIyBNdWx0aXBseS4KCmRlZiBfbXVsMShhLCB4LCBiYXNlKToKICAgIG4gPSAxICsgbGVuKGEpCiAgICByZXR1cm4gX3plcm9yZWR1Y2UoX2lucGxhY2VfbXVsYyhfemVyb2V4dGVuZChhLCBuKSwgeCwgMCwgYmFzZSlbMV0pCgpkZWYgX211bChhLCBiLCBiYXNlKToKICAgIGlmIF9pc3plcm8oYik6CiAgICAgICAgcmV0dXJuIFswXQogICAgcmV0dXJuIF9hZGQoX211bDEoYSwgYlswXSwgYmFzZSksIF9tdWwobnNobChhLCAxKSwgbnNocihiLCAxKSwgYmFzZSksCiAgICAgICAgICAgICAgICBiYXNlKQoKZGVmIG5tdWwoYSwgcywgYiwgdCwgYmFzZSk6CiAgICByZXR1cm4gX2ZpeHNpZ24oX211bChhLCBiLCBiYXNlKSwgcyAhPSB0KQoKIyBUZXN0LgoKZGVmIF90ZXN0KG4sIG9wKToKICAgIHcgPSBOdW0uYmFzZQogICAgeiA9ICgwLCAxLCAtMSwgdywgLXcsIHctMSwgMS13KQogICAgZm9yIHgsIHkgaW4gaXRlcnRvb2xzLnByb2R1Y3QoeiwgcmVwZWF0PTIpOgogICAgICAgIHUgPSBpbnQoc3RyKG9wKE51bSh4KSwgTnVtKHkpKSkpCiAgICAgICAgdiA9IG9wKHgsIHkpCiAgICAgICAgYXNzZXJ0IHUgPT0gdiwgZid7b3B9KHt4fSwge3l9KVxuRXhwZWN0ZWQ6e3Z9LCBHb3Q6e3V9JwogICAgdyA9IE51bS5iYXNlICoqIDMKICAgIGZvciBfIGluIHJhbmdlKG4pOgogICAgICAgIHggPSByYW5kb20ucmFuZGludCgtdywgdykKICAgICAgICB5ID0gcmFuZG9tLnJhbmRpbnQoLXcsIHcpCiAgICAgICAgdSA9IGludChzdHIob3AoTnVtKHgpLCBOdW0oeSkpKSkKICAgICAgICB2ID0gb3AoeCwgeSkKICAgICAgICBhc3NlcnQgdSA9PSB2LCBmJ3tvcH0oe3h9LCB7eX0pXG5FeHBlY3RlZDp7dn0sIEdvdDp7dX0nCgpuID0gMTAwMApfdGVzdChuLCBvcGVyYXRvci5hZGQpCl90ZXN0KG4sIG9wZXJhdG9yLnN1YikKX3Rlc3Qobiwgb3BlcmF0b3IubXVsKQoKZGVmIHNob3cxKGEpOgogICAgcHJpbnQocmVwcihhKSwgYSwgc2VwPSc7ICcpCgpkZWYgX3Nob3coeiwgb3ApOgogICAgcHJpbnQob3ApCiAgICBmb3IgeCwgeSBpbiBpdGVydG9vbHMucHJvZHVjdCh6LCByZXBlYXQ9Mik6CiAgICAgICAgc2hvdzEob3AoTnVtKHgpLCBOdW0oeSkpKQoKdyA9IE51bS5iYXNlCnogPSAoMCwgMSwgLTEsIHcsIC13KQpfc2hvdyh6LCBvcGVyYXRvci5hZGQpCl9zaG93KHosIG9wZXJhdG9yLnN1YikKX3Nob3coeiwgb3BlcmF0b3IubXVsKQoKZGVmIGZhY3RvcmlhbChuKToKICAgIHIgPSBOdW0oMSkKICAgIGZvciBpIGluIHJhbmdlKDIsIG4rMSk6CiAgICAgICAgciAqPSBOdW0oaSkKICAgIHJldHVybiByCgpwcmludChmYWN0b3JpYWwpCmZvciBpIGluIHJhbmdlKDUpOgogICAgc2hvdzEoZmFjdG9yaWFsKDEwKmkpKQ==