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>.
m = int(input())

def get(cur, need, x, y):
    ret = [cur]
    for i in range(2 * m):
        cur = (cur * x + y) % m
        ret.append(cur)

    if need not in ret:
        return None, 0

    idx = ret.index(need)
    
    if need not in ret[idx + 1:]:
        return idx, None

    idx2 = ret.index(need, idx + 1)

    return (idx, idx2 - idx)

def on_path(p, c, x):
    if x < p or (x - p) % c:
        return -1
    return x
    
def get_min(p1, c1, p2, c2):
    for t1 in range(2 * m):
        x = p1 + t1 * c1
        if x >= p2 and (x - p2) % c2 == 0:
            return x
    return -1

h1, a1 = map(int, input().split())
x1, y1 = map(int, input().split())
h2, a2 = map(int, input().split())
x2, y2 = map(int, input().split())

to1, c1 = get(h1, a1, x1, y1)
to2, c2 = get(h2, a2, x2, y2)

if to1 == None or to2 == None:
    print('-1')
else:
    if c1 == None and c2 == None:
        print(to1 if to1 == to2 else '-1')
    elif c1 == None:
        print(on_path(to2, c2, to1))
    elif c2 == None:
        print(on_path(to1, c1, to2))
    else:
        print(min(get_min(to1, c1, to2, c2), get_min(to2, c2, to1, c1)))
