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>.
def failure ():
    print(-1)
    exit()

def bezout (a, b):
    if b == 0:
        return (1, 0)
    (p, q) = bezout(b, a % b)
    return (q, p - (a // b) * q)

def gcd (a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

MAX_M = int(1e6 + 5)

pos = [[-1, -1] for i in range(MAX_M)]
tar = [0, 0]
lens = [0, 0]

m = int(input())
for k in range(2):
    (ini, tar[k]) = map(int, input().split(" "))
    (lin, fre) = map(int, input().split(" "))

    cur = ini
    while True:
        pos[cur][k] = lens[k]
        lens[k] += 1
        cur = (lin * cur + fre) % m
        if cur == ini:
            break

if pos[tar[0]][0] == -1 or pos[tar[1]][1] == -1:
    failure()

ks = [pos[tar[0]][0], pos[tar[1]][1]]
gc = gcd(lens[0], lens[1])
if ks[0] % gc != ks[1] % gc:
    failure()

lens[1] //= gc
ks[1] %= lens[1]

(u, v) = bezout(lens[0], lens[1])
ans = u * lens[0] * ks[1] + v * lens[1] * ks[0]
print(ans)
