Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is *h*<sub class="lower-index">1</sub> and height of Abol is *h*<sub class="lower-index">2</sub>. Each second, Mike waters Abol and Xaniar.

So, if height of Xaniar is *h*<sub class="lower-index">1</sub> and height of Abol is *h*<sub class="lower-index">2</sub>, after one second height of Xaniar will become <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2fe18334e8025eeb03e58258a1a73999e06eaded.png" style="max-width: 100.0%;max-height: 100.0%;"/> and height of Abol will become <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/fc063cc983b60502463ef52c01f1c9f44150fd93.png" style="max-width: 100.0%;max-height: 100.0%;"/> where *x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> and *y*<sub class="lower-index">2</sub> are some integer numbers and <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/57fc4a50a6c33bac9327d8c392910a6dbf5c89bb.png" style="max-width: 100.0%;max-height: 100.0%;"/> denotes the remainder of *a* modulo *b*.

Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is *a*<sub class="lower-index">1</sub> and height of Abol is *a*<sub class="lower-index">2</sub>.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.
The first line of input contains integer *m* (2 ≤ *m* ≤ 10<sup class="upper-index">6</sup>).

The second line of input contains integers *h*<sub class="lower-index">1</sub> and *a*<sub class="lower-index">1</sub> (0 ≤ *h*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">1</sub> &lt; *m*).

The third line of input contains integers *x*<sub class="lower-index">1</sub> and *y*<sub class="lower-index">1</sub> (0 ≤ *x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub> &lt; *m*).

The fourth line of input contains integers *h*<sub class="lower-index">2</sub> and *a*<sub class="lower-index">2</sub> (0 ≤ *h*<sub class="lower-index">2</sub>, *a*<sub class="lower-index">2</sub> &lt; *m*).

The fifth line of input contains integers *x*<sub class="lower-index">2</sub> and *y*<sub class="lower-index">2</sub> (0 ≤ *x*<sub class="lower-index">2</sub>, *y*<sub class="lower-index">2</sub> &lt; *m*).

It is guaranteed that *h*<sub class="lower-index">1</sub> ≠ *a*<sub class="lower-index">1</sub> and *h*<sub class="lower-index">2</sub> ≠ *a*<sub class="lower-index">2</sub>.
import sys



input       = []
input_index = 0

def next(type, number = None):
	def next():
		global input, input_index
		
		
		if input_index == len(input):
			if sys.stdin:
				input       = sys.stdin.readline().split()
				input_index = 0
			else:
				raise Exception()
				
				
		input_index += 1
		
		return input[input_index - 1]
		
		
	if number is None:
		result = type(next())
	else:
		result = [type(next()) for _ in range(number)]
		
	return result
	
	
	
def gcd(a, b):
	a, b = min(a, b), max(a, b)
	
	while b % a != 0:
		a, b = b % a, a
		
	return a
	
def lcm(a, b):
	return (a * b) // gcd(a, b)
	
	
	
m = next(int)

h1, a1, x1, y1 = next(int, 4)
h2, a2, x2, y2 = next(int, 4)


def form_ts(h, a, x, y):
	ts    = [None] * m
	ts[h] = 0
	
	for t in range(1, m + 1):
		h = (x * h + y) % m
		
		if ts[h] is None:
			ts[h] = t
		else:
			p = t
			break
			
	return ts, ts[a], p
	
ts1, mt1, p1 = form_ts(h1, a1, x1, y1)
ts2, mt2, p2 = form_ts(h2, a2, x2, y2)


if (mt1 is not None) and (mt1 is not None):
	n = lcm(p1, p2) // p1
	
	for i in range(n):
		t = i * p1 + mt1
		
		if t % p2 == mt2:
			print(t)
			break
	else:
		print(-1)
else:
	print(-1)
	