Alice is feeling bored while sitting on the riverbank with her sister, when she notices a 2D White Rabbit with a 2D pocket watch run past. She follows it down a rabbit hole when suddenly she falls a long way to a curious 2D plane.

In this 2D plane she discovered she can only move using a sequence of movements. Those movements are limited to:

Scaling, denoted as $S_{c}$ (where ${c}$ is a nonzero rational number). If Alice is currently at $(x,y)$, then $S_{c}$ takes her to $(cx,cy)$.
Translation, denoted as $T_{a,b}$ (where ${a}$ and ${b}$ are rational numbers). If Alice is currently at $(x,y)$, then $T_{a,b}$ takes her to $(a+x,b+y)$.
Rotation, denoted as $R_{a,b}$ (where ${a}$ and ${b}$ are rational numbers and $a^2+b^2=1$). If Alice is currently at $(x,y)$, then $R_{a,b}$ takes her to $(ax+by,ay-bx)$. In other words, $R_{a,b}$ is a clockwise rotation about the origin, at an angle $\theta$ where $\text{cos}\theta=a$ and $\sin\theta=b$.
Flip X-axis, denoted as $\mathbf{F}_{X}$. If Alice is currently at $(x,y)$, then $\mathbf{F}_{X}$ takes her to $(x,-y)$.
Flip Y-axis, denoted as $\mathbf{F}_{Y}$. If Alice is currently at $(x,y)$, then $\mathbf{F}_{Y}$ takes her to $(-x,y)$.
Inversion, denoted as ${I}$ (more precisely, inversion in the unit circle). If Alice is currently at $(x,y)$, then ${I}$ takes her to $\left(\frac{x}{x^2+y^2},\frac{y}{x^2+y^2}\right)$.

Also, Alice discovered that when she is at $(0,0)$ before she performs an inversion, she is taken to a special place called Wonderland. In Wonderland, performing any of the other movements (scaling, translation, rotation or flip) will return her to Wonderland, and performing an inversion moves her back to $(0,0)$.

Now, Alice has a sequence of $N$ such movements to make. Moreover, she performs this sequence of $N$ movements a total of ${K}$ times. Your task is to determine her final location after her adventure.

If Alice's final location is $(x_f,y_f)$, it's easy to see that $x_f$ and $y_f$ are rational. Let $x_f=A/B$ and $y_f=C/D$ (both in lowest terms). Understandably, ${A}$, ${B}$, ${C}$ and ${D}$ can be really large integers, so instead of asking for $x_f$ and $y_f$ we will only ask for the values $AB^{-1}\:\text{mod}\:(10^9+7)$ and $CD^{-1}\:\text{mod}\:(10^9+7)$.

Input Format 

The first input contains a single integer, ${T}$, which is the number of test cases. The next lines contain the descriptions of the ${T}$ test cases.

The first line of each test case contains four values $N$, ${K}$, $x_s$ and $y_s$. $N$ and ${K}$ are integers (described above), and $(x_s,y_s)$ is the initial location of Alice ($x_s$ and $y_s$ are rational numbers).

The next $N$ lines each contains the description of a movement in the sequence, which is one of the following:

S c, which denotes scaling (${c}$ is a nonzero rational number),
T a b, which denotes translation (${a}$ and ${b}$ are rational numbers),
R a b, which denotes rotation (${a}$ and ${b}$ are rational numbers and $a^2+b^2=1$),
F X, which denotes flip X-axis,
F Y, which denotes flip Y-axis, and
I, which denotes inversion.

Output Format 

If Alice's final location is Wonderland, output WONDERLAND.

If Alice's final location is $(x_f,y_f)$, and $x_f=A/B$ and $y_f=C/D$ in irreducible form, then output the two integers $AB^{-1}\:\text{mod}\:(10^9+7)$ and $CD^{-1}\:\text{mod}\:(10^9+7)$ in a line separated by a single space. However, if either ${B}$ or ${D}$ is not invertible, also output WONDERLAND.  

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq10^5$ 

The sum of the $N$'s in a single test file is $\leq10^5$ 

$1\leq K\leq10^{15}$ 

Each rational number is expressed in irreducible form $A/B$ with the following constraints: 

$-10^9<A<10^9$ 

$1\leq B<10^9$  

Sample Input  

2
3 2 0/1 0/1
T -2/1 3/1
R 3/5 4/5
I
5 1 2/1 -2/1
F X
S 3/2
T -3/1 -3/1
I
F Y

Sample Output  

881896558 492241383
WONDERLAND

Explanation 

In the first test case, $(x_s,y_s)=(0,0)$, $K=2$ and the sequence of operations is $[T_{-2,3},R_{3/5,4/5},I]$.

$\begin{array}{ccccc}T_{-2,3}:&\text{(0,0)}&\to&\text{(-2,3)}\\ R_{3/5,4,5}:&\text{(-2,3)}&\to&\text{(6/5,17/5)}\\ I:&\text{(6/5,17/5)}&\to&\text{(6/65,17/65)}\\ T_{-2,3}:&\text{(6/65,17/65)}&\to&\text{(-124/65,22/65)}\\ R_{3/5,4,5}:&\text{(-124/65,212/165)}&\to&\text{(476/325,1132/325)}\\ I:&\text{(476/325,1132/325)}&\to&\text{(119/1160,2831160)}\\ \end{array}$  

Therefore, the final location is $(x_f,y_f)=(119/1160,283/1160)$. So we print: 

$119\cdot1160^{-1}\:\text{mod}\:(10^9+7)=881896558$ and: 

$283\cdot1160^{-1}\:\text{mod}\:(10^9+7)=492241383$.  

In the second test case, $(x_s,y_s)=(2,-2)$, $K=1$ and the sequence of operations is $[F_X,S_{3/2},T_{-3,-3},I,F_Y]$.

$\begin{aligned}F_X\colon&(2,-2)&\to&(2,2)\\ S_{3/2}\colon&(2,2)&\to&(3,3)\\ T_{-3,-3}\colon&(3,3)&\to&(0,0)\\ I\colon&(0,0)&\to&\text{Wonderland}\\F_Y\colon&
\text{Wonderland}&\to&\text{Wonderland}\end{aligned}$  

Therefore, the final location is Wonderland.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
def add(x, y):
	return (x[0] + y[0], x[1] + y[1])

def mod(x, p):
	return (x[0] % p, x[1] % p)

def conj(x):
	return (x[0], -x[1])

def mult(x, y):
	return (x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0])

def prod(M, N, p):
	return [[mod(add(mult(M[0][0], N[0][0]), mult(M[0][1], N[1][0])), p), mod(add(mult(M[0][0], N[0][1]), mult(M[0][1], N[1][1])), p)], [mod(add(mult(M[1][0], N[0][0]), mult(M[1][1], N[1][0])), p), mod(add(mult(M[1][0], N[0][1]), mult(M[1][1], N[1][1])), p)]]

def puiss(M, n, r):
	L = [M]
	i = 1
	while i < n:
		L += [prod(L[-1], L[-1], r)]
		i *= 2
	e = 0
	N = [[(int(i == j), 0) for j in range(len(M))] for i in range(len(M))]
	while n:
		if n % 2:
			N = prod(N, L[e], r)
		n //= 2
		e += 1
	return N

def coeff(s, p):
	(n, d) = map(int, s.split('/'))
	return n * pow(d, p - 2, p) % p
nbtests = int(input())
p = 10 ** 9 + 7
for _ in range(nbtests):
	(n, k, px, py) = input().split()
	(n, k) = (int(n), int(k))
	px = coeff(px, p)
	py = coeff(py, p)
	(a, b, c, d, s) = ((1, 0), (0, 0), (0, 0), (1, 0), 0)
	for i_op in range(n):
		q = input().split()
		if q[0] == 'I':
			(a, b, c, d, s) = (conj(c), conj(d), conj(a), conj(b), (s + 1) % 2)
		elif q[0] == 'F':
			if q[1] == 'X':
				(a, b, c, d, s) = (conj(a), conj(b), conj(c), conj(d), (s + 1) % 2)
			else:
				(a, b, c, d, s) = (mult((-1, 0), conj(a)), mult((-1, 0), conj(b)), conj(c), conj(d), (s + 1) % 2)
		elif q[0] in ['S', 'R']:
			u = coeff(q[1], p)
			v = 0
			if q[0] == 'R':
				v = -coeff(q[2], p) % p
			z = (u, v)
			(a, b) = (mult(z, a), mult(z, b))
		else:
			u = coeff(q[1], p)
			v = coeff(q[2], p)
			z = (u, v)
			(a, b) = (add(a, mult(z, c)), add(b, mult(z, d)))
		(a, b, c, d) = (mod(a, p), mod(b, p), mod(c, p), mod(d, p))
	if s == 0:
		M = puiss([[a, b], [c, d]], k, p)
	else:
		N1 = [[a, b], [c, d]]
		N2 = [[conj(a), conj(b)], [conj(c), conj(d)]]
		if k % 2:
			M = prod(N1, puiss(prod(N2, N1, p), k // 2, p), p)
		else:
			M = puiss(prod(N1, N2, p), k // 2, p)
	if s and k % 2:
		z = (px, -py % p)
	else:
		z = (px, py)
	num = add(mult(M[0][0], z), M[0][1])
	denom = add(mult(M[1][0], z), M[1][1])
	d = denom[0] * denom[0] + denom[1] * denom[1]
	if d % p == 0:
		print('WONDERLAND')
	else:
		sol = mod(mult(mult(num, conj(denom)), (pow(d, p - 2, p), 0)), p)
		print(str(sol[0]) + ' ' + str(sol[1]))


def add(x, y):
	return (x[0] + y[0], x[1] + y[1])

def mod(x, p):
	return (x[0] % p, x[1] % p)

def conj(x):
	return (x[0], -x[1])

def mult(x, y):
	return (x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0])

def prod(M, N, p):
	return [[mod(add(mult(M[0][0], N[0][0]), mult(M[0][1], N[1][0])), p), mod(add(mult(M[0][0], N[0][1]), mult(M[0][1], N[1][1])), p)], [mod(add(mult(M[1][0], N[0][0]), mult(M[1][1], N[1][0])), p), mod(add(mult(M[1][0], N[0][1]), mult(M[1][1], N[1][1])), p)]]

def puiss(M, n, r):
	L = [M]
	i = 1
	while i < n:
		L += [prod(L[-1], L[-1], r)]
		i *= 2
	e = 0
	N = [[(int(i == j), 0) for j in range(len(M))] for i in range(len(M))]
	while n:
		if n % 2:
			N = prod(N, L[e], r)
		n //= 2
		e += 1
	return N

def coeff(s, p):
	(n, d) = map(int, s.split('/'))
	return n * pow(d, p - 2, p) % p
nbtests = int(input())
p = 10 ** 9 + 7
for _ in range(nbtests):
	(n, k, px, py) = input().split()
	(n, k) = (int(n), int(k))
	px = coeff(px, p)
	py = coeff(py, p)
	(a, b, c, d, s) = ((1, 0), (0, 0), (0, 0), (1, 0), 0)
	for i_op in range(n):
		q = input().split()
		if q[0] == 'I':
			(a, b, c, d, s) = (conj(c), conj(d), conj(a), conj(b), (s + 1) % 2)
		elif q[0] == 'F':
			if q[1] == 'X':
				(a, b, c, d, s) = (conj(a), conj(b), conj(c), conj(d), (s + 1) % 2)
			else:
				(a, b, c, d, s) = (mult((-1, 0), conj(a)), mult((-1, 0), conj(b)), conj(c), conj(d), (s + 1) % 2)
		elif q[0] in ['S', 'R']:
			u = coeff(q[1], p)
			v = 0
			if q[0] == 'R':
				v = -coeff(q[2], p) % p
			z = (u, v)
			(a, b) = (mult(z, a), mult(z, b))
		else:
			u = coeff(q[1], p)
			v = coeff(q[2], p)
			z = (u, v)
			(a, b) = (add(a, mult(z, c)), add(b, mult(z, d)))
		(a, b, c, d) = (mod(a, p), mod(b, p), mod(c, p), mod(d, p))
	if s == 0:
		M = puiss([[a, b], [c, d]], k, p)
	else:
		N1 = [[a, b], [c, d]]
		N2 = [[conj(a), conj(b)], [conj(c), conj(d)]]
		if k % 2:
			M = prod(N1, puiss(prod(N2, N1, p), k // 2, p), p)
		else:
			M = puiss(prod(N1, N2, p), k // 2, p)
	if s and k % 2:
		z = (px, -py % p)
	else:
		z = (px, py)
	num = add(mult(M[0][0], z), M[0][1])
	denom = add(mult(M[1][0], z), M[1][1])
	d = denom[0] * denom[0] + denom[1] * denom[1]
	if d % p == 0:
		print('WONDERLAND')
	else:
		sol = mod(mult(mult(num, conj(denom)), (pow(d, p - 2, p), 0)), p)
		print(str(sol[0]) + ' ' + str(sol[1]))


def add(x, y):
	return (x[0] + y[0], x[1] + y[1])

def mod(x, p):
	return (x[0] % p, x[1] % p)

def conj(x):
	return (x[0], -x[1])

def mult(x, y):
	return (x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0])

def prod(M, N, p):
	return [[mod(add(mult(M[0][0], N[0][0]), mult(M[0][1], N[1][0])), p), mod(add(mult(M[0][0], N[0][1]), mult(M[0][1], N[1][1])), p)], [mod(add(mult(M[1][0], N[0][0]), mult(M[1][1], N[1][0])), p), mod(add(mult(M[1][0], N[0][1]), mult(M[1][1], N[1][1])), p)]]

def puiss(M, n, r):
	L = [M]
	i = 1
	while i < n:
		L += [prod(L[-1], L[-1], r)]
		i *= 2
	e = 0
	N = [[(int(i == j), 0) for j in range(len(M))] for i in range(len(M))]
	while n:
		if n % 2:
			N = prod(N, L[e], r)
		n //= 2
		e += 1
	return N

def coeff(s, p):
	(n, d) = map(int, s.split('/'))
	return n * pow(d, p - 2, p) % p
nbtests = int(input())
p = 10 ** 9 + 7
for _ in range(nbtests):
	(n, k, px, py) = input().split()
	(n, k) = (int(n), int(k))
	px = coeff(px, p)
	py = coeff(py, p)
	(a, b, c, d, s) = ((1, 0), (0, 0), (0, 0), (1, 0), 0)
	for i_op in range(n):
		q = input().split()
		if q[0] == 'I':
			(a, b, c, d, s) = (conj(c), conj(d), conj(a), conj(b), (s + 1) % 2)
		elif q[0] == 'F':
			if q[1] == 'X':
				(a, b, c, d, s) = (conj(a), conj(b), conj(c), conj(d), (s + 1) % 2)
			else:
				(a, b, c, d, s) = (mult((-1, 0), conj(a)), mult((-1, 0), conj(b)), conj(c), conj(d), (s + 1) % 2)
		elif q[0] in ['S', 'R']:
			u = coeff(q[1], p)
			v = 0
			if q[0] == 'R':
				v = -coeff(q[2], p) % p
			z = (u, v)
			(a, b) = (mult(z, a), mult(z, b))
		else:
			u = coeff(q[1], p)
			v = coeff(q[2], p)
			z = (u, v)
			(a, b) = (add(a, mult(z, c)), add(b, mult(z, d)))
		(a, b, c, d) = (mod(a, p), mod(b, p), mod(c, p), mod(d, p))
	if s == 0:
		M = puiss([[a, b], [c, d]], k, p)
	else:
		N1 = [[a, b], [c, d]]
		N2 = [[conj(a), conj(b)], [conj(c), conj(d)]]
		if k % 2:
			M = prod(N1, puiss(prod(N2, N1, p), k // 2, p), p)
		else:
			M = puiss(prod(N1, N2, p), k // 2, p)
	if s and k % 2:
		z = (px, -py % p)
	else:
		z = (px, py)
	num = add(mult(M[0][0], z), M[0][1])
	denom = add(mult(M[1][0], z), M[1][1])
	d = denom[0] * denom[0] + denom[1] * denom[1]
	if d % p == 0:
		print('WONDERLAND')
	else:
		sol = mod(mult(mult(num, conj(denom)), (pow(d, p - 2, p), 0)), p)
		print(str(sol[0]) + ' ' + str(sol[1]))