#!/usr/bin/env python3

from sympy import sqrt, log, ceiling, Integer
from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import inverse

N = 11081631875903145989449935723431993312048263659503073501368579288661507666926127398551161494057149306128113773163942639308834214121175806650609216999457699806761832905200688030797211656004392019494461369905299150414106039926917206543955359193966893148964232596310365304968051716316421386564037673515738090636958039103706945349258789436043666088184674948218539196263599899299117746103356732914111330139176914363944699056706536973601851519543254647327613986429683489937828404640743341705415177790924588759219148196121101333618974290049804819348181073769764832469557718828674823915162708288827812462173689965257895702511
e = 65537
m = int(open("message.txt", "r").read().strip())

def is_square(n):
    return type(sqrt(n)) == Integer

def fermat_factor(n):

    num_digits = int(log(n, 10).evalf() + 1)
    a = ceiling( sqrt(n).evalf(num_digits) )

    while not is_square(a * a - n):
        a += 1

    b = sqrt(a * a - n)

    return (a + b, a - b)

p, q = fermat_factor(N)
d = inverse(e, (p - 1) * (q - 1))

decrypted = pow(m, int(d), N)

print(long_to_bytes(decrypted).decode("utf-8"))
