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
from heapq import *
sys.setrecursionlimit(5000)

m=0
h,a,x,y = [0]*2,[0]*2,[0]*2,[0]*2

#sys.stdin = open('test.txt')

def f(h0,x,y,n):
	for i in range(n):
		h0 = (y+x*h0)%m
	return h0

def fto(h0,x,y,a):
	vis = [-1 for i in range(m)]
	vis[h0]=0
	while(h0!=a):
		nh0 = (x*h0+y)%m
		if(nh0!=a and vis[nh0]!=-1): return -1
		vis[nh0]=vis[h0]+1
		h0=nh0
	return vis[a]

def solve():
	t0 = fto(h[0],x[0],y[0],a[0])
	c = f(h[1],x[1],y[1],t0)
	t  = fto((x[0]*a[0]+y[0])-1,x[0],y[0],a[0])-1
	for i in range(m+5):
		if( c == a[1]): return t0+i
		c = (t*c+(y[1]*t0)%m) % m
	return -1

for line in sys.stdin:
	m = int(line)
	h[0],a[0] = (int(x) for x in input().split())
	x[0],y[0] = (int(x) for x in input().split())
	h[1],a[1] = (int(x) for x in input().split())
	x[1],y[1] = (int(x) for x in input().split())
	print(solve())
