import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False

    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True

import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False
    k = (m + n // m) // 2
    while k != m:
        m, k = k, (m + n // m) // 2
    if m * m == n:
        return False
    
    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True
    

n = 3317044064679887385961981
m = n // 2
print(isprime(3317044064679887385961981*3317044064679887385961981))

#for i in range (2, 44):
#    print (i, pow(i,m,n), jacobi(i,n))