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>.
__author__ = '$'
import sys
sys.stdin = open("in.txt")
def solve(h, a, x, y):
    global m
    res1 = 1
    res2 = 1
    tmp = h
    h = (x * h + y) % m
    flag = False if h != a else True
    while h != tmp:
        res2 += 1
        if flag == False:
            res1 += 1
        h = (x * h +y) % m
        if h == a:
            flag = True

    if flag == False:
        res1 = -1

    return [res1, res2]
def GCD(x, y):
    return x if y == 0 else GCD(y, x%y)
def LCM(x, y):
    return x * y // GCD(x, y)
try:
    while True:
        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(" "))
        T1 = solve(h1, a1, x1, y1)
        T2 = solve(h2, a2, x2, y2)
        t1 = T1[0]
        t2 = T2[0]
        r1 = T1[1]
        r2 = T2[1]
        if t1 == -1 or t2 == -1:
            print("-1")
        else:
            for i in range(1000001):
                if (i * r1 + t1) % r2 == t2 or (i * r1 + t1)  == t2:
                    ans = i
                    break
            print(ans * r1 + t1)
except EOFError:
    pass