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_1 and height of Abol is h_2. Each second, Mike waters Abol and Xaniar.

 [Image] 

So, if height of Xaniar is h_1 and height of Abol is h_2, after one second height of Xaniar will become $(x_{1} h_{1} + y_{1}) \operatorname{mod} m$ and height of Abol will become $(x_{2} h_{2} + y_{2}) \operatorname{mod} m$ where x_1, y_1, x_2 and y_2 are some integer numbers and $a \operatorname{mod} b$ 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_1 and height of Abol is a_2.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.


-----Input-----

The first line of input contains integer m (2 ≤ m ≤ 10^6).

The second line of input contains integers h_1 and a_1 (0 ≤ h_1, a_1 < m).

The third line of input contains integers x_1 and y_1 (0 ≤ x_1, y_1 < m).

The fourth line of input contains integers h_2 and a_2 (0 ≤ h_2, a_2 < m).

The fifth line of input contains integers x_2 and y_2 (0 ≤ x_2, y_2 < m).

It is guaranteed that h_1 ≠ a_1 and h_2 ≠ a_2.


-----Output-----

Print the minimum number of seconds until Xaniar reaches height a_1 and Abol reaches height a_2 or print -1 otherwise.


-----Examples-----
Input
5
4 2
1 1
0 1
2 3

Output
3

Input
1023
1 2
1 0
1 2
1 1

Output
-1



-----Note-----

In the first sample, heights sequences are following:

Xaniar: $4 \rightarrow 0 \rightarrow 1 \rightarrow 2$

Abol: $0 \rightarrow 3 \rightarrow 4 \rightarrow 1$

Difficulty: HARD
Tags: Mathematics

Complete search

Implementation

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
f = lambda : map(int, input().split())
m = int(input())

def g():
	(h, a) = f()
	(x, y) = f()
	t = lambda : (h * x + y) % m
	(s, d) = (0, 1)
	while h != a:
		h = t()
		s += 1
		if s > m:
			print(-1)
			exit()
	h = t()
	while h != a:
		h = t()
		d += 1
		if d > m:
			return (s, 0)
	return (s, d)

def h():
	(u, x) = g()
	(v, y) = g()
	k = 0
	while u != v:
		if u < v:
			u += x
		else:
			v += y
		k += 1
		if k > 2 * m:
			return -1
	return u
print(h())


__author__ = 'kitkat'
import sys

def GetNext(h, x, y):
	nonlocal m
	return (x * h + y) % m
try:
	while True:
		m = int(input())
		(h1, a1) = list(map(int, input().split(' ')))
		(x1, y1) = list(map(int, input().split(' ')))
		(h2, a2) = list(map(int, input().split(' ')))
		(x2, y2) = list(map(int, input().split(' ')))
		t1 = []
		t2 = []
		T = 0
		for i in range(2 * m + 1):
			if h1 == a1:
				t1.append(T)
			if h2 == a2:
				t2.append(T)
			T += 1
			h1 = GetNext(h1, x1, y1)
			h2 = GetNext(h2, x2, y2)
		if len(t1) == 0 or len(t2) == 0:
			print('-1')
			continue
		if t1[0] == t2[0]:
			print(t1[0])
			continue
		elif len(t1) < 2 or len(t2) < 2:
			if len(t1) == 1 and len(t2) == 1:
				print(t1[0] if t1[0] == t2[0] else '-1')
			elif len(t1) == 1:
				if t1[0] in t2:
					print(t1[0])
				else:
					print('-1')
			elif len(t2) == 1:
				if t2[0] in t1:
					print(t2[0])
				else:
					print('-1')
			continue
		res1 = t1[0]
		res2 = t2[0]
		flag = False
		for i in range(5000000):
			if res1 == res2:
				flag = True
				print(res1)
				break
			elif res1 <= res2:
				res1 += t1[1] - t1[0]
			else:
				res2 += t2[1] - t2[0]
		if not flag:
			print('-1')
except EOFError:
	pass


from fractions import *
f = lambda : map(int, input().split())
m = int(input())

def g(u, v):
	(h, a) = u
	(x, y) = v
	s = 0
	while h != a:
		h = (h * x + y) % m
		s += 1
		if s > m:
			break
	h = (a * x + y) % m
	d = 1
	while h != a:
		h = (h * x + y) % m
		d += 1
		if d > m:
			break
	return (s, d)
((u, x), (v, y)) = (g(f(), f()), g(f(), f()))
if u > m or v > m:
	q = -1
elif u == v:
	q = u
elif x > m:
	q = -1 if u < v or (v - u) % y else u
elif y > m:
	q = -1 if v < u or (v - u) % x else v
elif (v - u) % gcd(x, y):
	q = -1
else:
	while u != v:
		if u < v:
			u += x
		else:
			v += y
	q = u
print(q)


def main():
	(m, tt) = (int(input()), [0] * 4)
	for i in (0, 2):
		(h, a) = map(int, input().split())
		(x, y) = map(int, input().split())
		ha = (h, a)
		for t in range(1, m * 2):
			h = (h * x + y) % m
			if h in ha:
				if h == ha[0]:
					if tt[i]:
						tt[i] = t - tt[i]
						break
					else:
						tt[i] = t
				elif tt[i + 1]:
					tt[i] = t - tt[i + 1]
					break
				else:
					tt[i + 1] = t
	(step1, shift1, step2, shift2) = tt if tt[0] > tt[2] else tt[2:] + tt[:2]
	if shift1 == shift2 != 0:
		print(shift1)
		return
	if step1 and (not step2) and shift1 and (shift1 <= shift2) and (not (shift2 - shift1) % step1):
		print(shift2)
		return
	if all(tt):
		if step2 == 1:
			print(shift1 if shift1 >= shift2 else shift2 + (shift2 - shift1) % step1)
			return
		for t in range(shift1 - shift2, shift1 - shift2 + step1 * step2, step1):
			if not t % step2:
				print(t + shift2)
				return
	print(-1)
main()


mod = int(input())
(h1, a1) = map(int, input().split())
(x1, y1) = map(int, input().split())
(h2, a2) = map(int, input().split())
(x2, y2) = map(int, input().split())
q1 = 0
while h1 != a1:
	h1 = (h1 * x1 + y1) % mod
	q1 += 1
	if q1 > 2 * mod:
		print(-1)
		return
q2 = 0
t2 = h2
while t2 != a2:
	t2 = (t2 * x2 + y2) % mod
	q2 += 1
	if q2 > 2 * mod:
		print(-1)
		return
if q1 == q2:
	print(q1)
	return
c1 = 1
h1 = (a1 * x1 + y1) % mod
while h1 != a1:
	h1 = (h1 * x1 + y1) % mod
	c1 += 1
	if c1 > 2 * mod:
		print(-1)
		return
c2 = 0
nx2 = 1
ny2 = 0
for i in range(c1):
	nx2 = nx2 * x2 % mod
	ny2 = (ny2 * x2 + y2) % mod
for i in range(q1):
	h2 = (h2 * x2 + y2) % mod
while h2 != a2:
	h2 = (h2 * nx2 + ny2) % mod
	c2 += 1
	if c2 > 2 * mod:
		print(-1)
		return
print(q1 + c1 * c2)


import fractions

def read_data():
	m = int(input())
	(h1, a1) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(h2, a2) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	return (m, h1, a1, x1, y1, h2, a2, x2, y2)

def solve(m, h1, a1, x1, y1, h2, a2, x2, y2):
	t = 0
	h1s = [-1] * m
	h2s = [-1] * m
	h1s[h1] = 0
	h2s[h2] = 0
	t1 = -1
	t2 = -1
	while h1 != a1 or h2 != a2:
		t += 1
		h1 = (x1 * h1 + y1) % m
		h2 = (x2 * h2 + y2) % m
		if h1s[h1] >= 0 and t1 == -1:
			t1 = h1s[h1]
			s1 = t - t1
			if t2 >= 0:
				break
		else:
			h1s[h1] = t
		if h2s[h2] >= 0 and t2 == -1:
			t2 = h2s[h2]
			s2 = t - t2
			if t1 >= 0:
				break
		else:
			h2s[h2] = t
	if h1 == a1 and h2 == a2:
		return t
	return retrieve(a1, a2, t1, s1, t2, s2, h1s, h2s)

def retrieve(a1, a2, t1, s1, t2, s2, h1s, h2s):
	u1 = h1s[a1]
	u2 = h2s[a2]
	if u1 == -1 or u2 == -1:
		return -1
	if u1 < t1:
		if guess(h2s, u1, t2, s2, a2):
			return u1
		else:
			return -1
	if u2 < t2:
		if guess(h1s, u2, t1, s1, a1):
			return u2
		else:
			return -1
	return find_time(u1, s1, u2, s2)

def guess(hs, u, t, s, a):
	if u <= t:
		return hs[a] == u
	tt = t + (u - t) % s
	return hs[a] == tt

def find_time(u1, s1, u2, s2):
	g = fractions.gcd(s1, s2)
	if abs(u1 - u2) % g:
		return -1
	(k1, k2) = extended_euclid(s1, s2, u2 - u1, g)
	b = s2 // g
	return k1 % b * s1 + u1

def egcd(a, b):
	(x, lastx) = (0, 1)
	(y, lasty) = (1, 0)
	while b:
		q = a // b
		(a, b) = (b, a % b)
		(x, lastx) = (lastx - q * x, x)
		(y, lasty) = (lasty - q * y, y)
	return (lastx, lasty)

def extended_euclid(a, b, c, g):
	(x, y) = egcd(a, b)
	return (c // g * x, x // g * y)
param = read_data()
print(solve(*param))