import random


def IsPrime(n):
    d = 2
    while n % d != 0:
        d += 1
    return d == n


p = random.randint(500000, 3000000)
while IsPrime(p) == False:
    p = random.randint(500000, 3000000)

x = 3
q = 0
while x < p - 1:
    if (p - 1) % x == 0:
        if IsPrime(x) == True:
            q = x
    x = x + 1
print(p)
print(q)
h = random.randint(1, p - 1)
a = (h ** ((p-1)//q)) % p
print(a)
k = random.randint(2, q-1)
x = random.randint(2, q-1)
y = a**x % p
s = input()
H = 0
for i in range (len(s)):
    H = H + bin(ord(s[i])).count('1')
print(H)
r = a**k % p % q
s = (x * r + k * H) % q
v = H**(q - 2) % q
z1 = s * v % q
z2 = (q - r) * v % q
u = ((a**z1 * y**z2) % p) % q
print(u, r)