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>.
from math import gcd


def opk(m, h, a, x, y):
    d = {}
    i = 0
    j = h
    while j not in d:
        d[j] = i
        j = (x*j + y) % m
        i += 1
    o = d[j]
    p = len(d) - o
    k = d.get(a)
    # log(m, h, a, x, y, '->', o, p, k)
    return o, p, k


def ea(a, b, g):
    r0, s0, t0 = a, 1, 0
    r1, s1, t1 = b, 0, 1
    while r1:
        q1, r2 = divmod(r1, r0)
        s2 = s0 - q1*s1
        t2 = t0 - q1*t1
        r0, s0, t0, r1, s1, t1 = r1, s1, t1, r2, s2, t2
    return s0, t0


def mins(m, h1, a1, x1, y1, h2, a2, x2, y2):
    o1, p1, k1 = opk(m, h1, a1, x1, y1)
    if k1 is None:
        return None
    o2, p2, k2 = opk(m, h2, a2, x2, y2)
    if k2 is None:
        return None
    if k1 == k2:
        return k1
    if k1 < o1 or k2 < o2:
        return None
    r1 = (o1 + k1) % p1
    r2 = (o2 + k2) % p2
    g = gcd(p1, p2)
    if (r1 - r2) % g != 0:
        return None
    s, t = ea(a, b, g)
    k = abs(r1 - r2) // g
    l = (p1 * p2) // g
    x = (r1 - (p1 * s * k)) % l
    if x < o1 or x < o2:
        x += l * ((max(o1, o2) - x + l - 1) // l)
    assert x >= o1
    assert x >= o2
    assert (x - o1) % p1 == k1
    assert (x - o2) % p2 == k2
    return x


def main():
    m = readint()
    h1, a1 = readinti()
    x1, y1 = readinti()
    h2, a2 = readinti()
    x2, y2 = readinti()
    print(mins(m, h1, a1, x1, y1, h2, a2, x2, y2) or -1)

##########

import sys
import time
import traceback
from contextlib import contextmanager
from io import StringIO

def readint():
    return int(input())


def readinti():
   return map(int, input().split())


def readintl():
   return list(readinti())


def readintll(k):
    return [readintl() for _ in range(k)]


def log(*args, **kwargs):
    print(*args, **kwargs, file=sys.stderr)


@contextmanager
def patchio(i):
    try:
        sys.stdin = StringIO(i)
        sys.stdout = StringIO()
        yield sys.stdout
    finally:
        sys.stdin = sys.__stdin__
        sys.stdout = sys.__stdout__


def do_test(k, test):
    try:
        log(f"TEST {k}")
        i, o = test
        with patchio(i) as r:
            t0 = time.time()
            main()
            t1 = time.time()
        if r.getvalue() == o:
            log(f"OK ({int((t1-t0)*1000000)/1000:0.3f} ms)\n")
        else:
            log(f"Expected:\n{o}"
                f"Got ({int((t1-t0)*1000000)/1000:0.3f} ms):\n{r.getvalue()}")
    except Exception:
        traceback.print_exc()
        log()


def test(ts):
    for k in ts or range(len(tests)):
        do_test(k, tests[k])


tests = [("""\
5
4 2
1 1
0 1
2 3
""", """\
3
"""), ("""\
1023
1 2
1 0
1 2
1 1
""", """\
-1
""")]


if __name__ == '__main__':
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('--test', '-t', type=int, nargs='*')
    args = parser.parse_args()
    main() if args.test is None else test(args.test)
