import sys input_data = sys.stdin.read().strip().split() if not input_data: sys.exit(0) X1 = int(input_data[0]) Y1 = int(input_data[1]) N = int(input_data[2]) MOD = 998244353 # Field extension element: a + b*w, with w^2 = -5. class Elem: __slots__ = ("a", "b") def __init__(self, a, b): self.a = a % MOD self.b = b % MOD def __add__(self, other): return Elem(self.a + other.a, self.b + other.b) def __sub__(self, other): return Elem(self.a - other.a, self.b - other.b) def __mul__(self, other): # (a + b*w)*(c + d*w) = (a*c - 5*b*d) + (a*d + b*c)*w return Elem(self.a * other.a - 5 * self.b * other.b, self.a * other.b + self.b * other.a) def __pow__(self, n): result = Elem(1, 0) base = self while n: if n & 1: result = result * base base = base * base n //= 2 return result def inv(self): # inverse of a + b*w is (a - b*w) / (a^2 + 5*b^2) norm = (self.a * self.a + 5 * self.b * self.b) % MOD inv_norm = pow(norm, MOD - 2, MOD) return Elem(self.a * inv_norm, -self.b * inv_norm) def __truediv__(self, other): return self * other.inv() def __repr__(self): return f"Elem({self.a}, {self.b})" # Create z1 = X1 + w*Y1 in the field extension. z1 = Elem(X1, Y1) # If z1 == 1 mod MOD, then each term equals 1, so X_n = 1, Y_n = 0. if z1.a % MOD == 1 and z1.b % MOD == 0: sx = N % MOD sy = 0 sys.stdout.write(f"{sx} {sy}\n") sys.exit(0) # Compute z1^N using fast exponentiation. z1N = z1 ** N # Compute the sum S = z1 + z1^2 + ... + z1^N. # Using the formula for a geometric series: # S = z1 * (z1^N - 1) / (z1 - 1) num = z1N - Elem(1, 0) S = z1 * num / (z1 - Elem(1, 0)) # S = U + w*V, so answer: Xsum = U, Ysum = V. sx = S.a % MOD sy = S.b % MOD sys.stdout.write(f"{sx} {sy}\n")