Our bear's forest has a checkered field. The checkered field is an n × n table, the rows are numbered from 1 to n from top to bottom, the columns are numbered from 1 to n from left to right. Let's denote a cell of the field on the intersection of row x and column y by record (x, y). Each cell of the field contains growing raspberry, at that, the cell (x, y) of the field contains x + y raspberry bushes.

The bear came out to walk across the field. At the beginning of the walk his speed is (dx, dy). Then the bear spends exactly t seconds on the field. Each second the following takes place:  Let's suppose that at the current moment the bear is in cell (x, y).  First the bear eats the raspberry from all the bushes he has in the current cell. After the bear eats the raspberry from k bushes, he increases each component of his speed by k. In other words, if before eating the k bushes of raspberry his speed was (dx, dy), then after eating the berry his speed equals (dx + k, dy + k).  Let's denote the current speed of the bear (dx, dy) (it was increased after the previous step). Then the bear moves from cell (x, y) to cell (((x + dx - 1) mod n) + 1, ((y + dy - 1) mod n) + 1).  Then one additional raspberry bush grows in each cell of the field. 

You task is to predict the bear's actions. Find the cell he ends up in if he starts from cell (sx, sy). Assume that each bush has infinitely much raspberry and the bear will never eat all of it.


-----Input-----

The first line of the input contains six space-separated integers: n, sx, sy, dx, dy, t (1 ≤ n ≤ 10^9; 1 ≤ sx, sy ≤ n;  - 100 ≤ dx, dy ≤ 100; 0 ≤ t ≤ 10^18).


-----Output-----

Print two integers — the coordinates of the cell the bear will end up in after t seconds.


-----Examples-----
Input
5 1 2 0 1 2

Output
3 1
Input
1 1 1 -1 -1 2

Output
1 1


-----Note-----

Operation a mod b means taking the remainder after dividing a by b. Note that the result of the operation is always non-negative. For example, ( - 1) mod 3 = 2.

In the first sample before the first move the speed vector will equal (3,4) and the bear will get to cell (4,1). Before the second move the speed vector will equal (9,10) and he bear will get to cell (3,1). Don't forget that at the second move, the number of berry bushes increased by 1.

In the second sample before the first move the speed vector will equal (1,1) and the bear will get to cell (1,1). Before the second move, the speed vector will equal (4,4) and the bear will get to cell (1,1). Don't forget that at the second move, the number of berry bushes increased by 1.

Difficulty: HARD
Tags: Matrices

Mathematics

Starter code:

Solutions:
(mod, sx, sy, dx, dy, t) = list(map(int, input().split()))

class Matrix:

	def __init__(self, n):
		self.n = n
		self.a = [[0] * n for _ in range(n)]

	def __mul__(self, b):
		res = Matrix(self.n)
		for i in range(self.n):
			for j in range(self.n):
				for k in range(self.n):
					res.a[i][j] += self.a[i][k] * b.a[k][j] % mod
					res.a[i][j] %= mod
		return res

	def __pow__(self, e):
		res = Matrix(self.n)
		for i in range(self.n):
			res.a[i][i] = 1
		tmp = self
		while e:
			if e & 1:
				res = res * tmp
			e >>= 1
			tmp = tmp * tmp
		return res
M = Matrix(6)
M.a = [[2, 1, 1, 0, 1, 2], [1, 2, 0, 1, 1, 2], [1, 1, 1, 0, 1, 2], [1, 1, 0, 1, 1, 2], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1]]
sx -= 1
sy -= 1
r = M ** t
f = lambda i: (r.a[i][0] * sx + r.a[i][1] * sy + r.a[i][2] * dx + r.a[i][3] * dy + r.a[i][5]) % mod + 1
print(f(0), f(1))


import functools
import itertools
import math

class NotAMatrixError(Exception):
	pass

class MatrixSizeError(Exception):

	def __init__(self, s1, s2):
		print('sizes do not match : ', s1, ', ', s2)

class NotSquareError(Exception):
	pass

class Matrix(list):

	def __init__(self, L):
		if type(L) == type(self):
			self = L
			return
		n = len(L)
		m = len(L[0])
		for i in range(n):
			if len(L[i]) != m:
				raise NotAMatrixError()
		list.__init__(self, L)
		self.n = n
		self.m = m
		self.degrees = []

	def check_size(self, M, mode):
		(n, m) = (len(M), len(M[0]))
		for i in range(n):
			if len(M[i]) != m:
				raise NotAMatrixError()
		if mode == 'add' and (self.n != n or self.m != m):
			raise MatrixSizeError((self.n, self.m), (n, m))
		if mode == 'lul' and self.m != n:
			print(self.m, n, self.m != n)
			raise MatrixSizeError((self.n, self.m), (n, m))

	def __add__(self, M):
		self.check_size(M, mode='add')
		return Matrix([[self[i][j] + M[i][j] for j in range(self.m)] for i in range(self.n)])

	def __iadd__(self, M):
		self.check_size(M, mode='add')
		for i in range(self.n):
			for j in range(self, m):
				self[i][j] += M[i][j]

	def __mul__(self, M):
		self.check_size(M, mode='mul')
		l = len(M[0])
		return Matrix([[sum((self[i][k] * M[k][j] for k in range(self.m))) for j in range(l)] for i in range(self.n)])

	def issquare(self):
		return self.n == self.m

	def primary(self):
		if self.n != self.m:
			raise NotSquareError()
		return Matrix([[int(i == j) for j in range(self.m)] for i in range(self.n)])

	def __pow__(self, n):
		if self.n != self.m:
			raise NotSquareError()
		if n == 0:
			return self.primary()
		elif n == 1:
			return self
		if len(self.degrees) == 0:
			self.degrees.append(self * self)
		for i in range(n.bit_length() - len(self.degrees) - 1):
			self.degrees.append(self.degrees[-1] * self.degrees[-1])
		s = [n >> i & 1 for i in range(1, n.bit_length())]
		res = functools.reduce(lambda x, y: x * y, itertools.compress(self.degrees, s))
		return res * self if n % 2 else res

	def drop_degrees(self):
		self.degrees.clear()

class Remainder(int):

	def __new__(self, n, p):
		obj = int.__new__(self, n % p)
		obj.p = p
		return obj

	def __mul__(self, m):
		return Remainder(int.__mul__(self, m), self.p)

	def __add__(self, m):
		return Remainder(int.__add__(self, m), self.p)

	def __sub__(self, m):
		return Remainder(int.__sub__(self, m), self.p)

	def __rmul__(self, m):
		return Remainder(int.__rmul__(self, m), self.p)

	def __radd__(self, m):
		return Remainder(int.__radd__(self, m), self.p)

	def __rsub__(self, m):
		return Remainder(int.__rsub__(self, m), self.p)

	def __neg__(self):
		return Remainder(int.__neg__(self), self.p)

	def __pow__(self, m):
		return Remainder(int.__pow__(self, m, self.p), self.p)

def solve(n, sx, sy, dx, dy, t):
	(o, l, j) = (Remainder(0, n), Remainder(1, n), Remainder(2, n))
	N = [[j, l, l, o, l, o], [l, j, o, l, l, o], [l, l, l, o, l, o], [l, l, o, l, l, o], [o, o, o, o, l, l], [o, o, o, o, o, l]]
	M = Matrix(N)
	(sx, sy, dx, dy) = [Remainder(x, n) for x in [sx, sy, dx, dy]]
	v = Matrix([[sx], [sy], [dx], [dy], [o], [l]])
	return M ** t * v
(n, sx, sy, dx, dy, t) = [int(x) for x in input().split()]
ans = solve(n, sx, sy, dx, dy, t)
print(int(ans[0][0] - 1) + 1, int(ans[1][0] - 1) + 1)