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_1 and height of Abol is h_2. Each second, Mike waters Abol and Xaniar.

 [Image] 

So, if height of Xaniar is h_1 and height of Abol is h_2, after one second height of Xaniar will become $(x_{1} h_{1} + y_{1}) \operatorname{mod} m$ and height of Abol will become $(x_{2} h_{2} + y_{2}) \operatorname{mod} m$ where x_1, y_1, x_2 and y_2 are some integer numbers and $a \operatorname{mod} b$ 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_1 and height of Abol is a_2.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.


-----Input-----

The first line of input contains integer m (2 ≤ m ≤ 10^6).

The second line of input contains integers h_1 and a_1 (0 ≤ h_1, a_1 < m).

The third line of input contains integers x_1 and y_1 (0 ≤ x_1, y_1 < m).

The fourth line of input contains integers h_2 and a_2 (0 ≤ h_2, a_2 < m).

The fifth line of input contains integers x_2 and y_2 (0 ≤ x_2, y_2 < m).

It is guaranteed that h_1 ≠ a_1 and h_2 ≠ a_2.


-----Output-----

Print the minimum number of seconds until Xaniar reaches height a_1 and Abol reaches height a_2 or print -1 otherwise.


-----Examples-----
Input
5
4 2
1 1
0 1
2 3

Output
3

Input
1023
1 2
1 0
1 2
1 1

Output
-1



-----Note-----

In the first sample, heights sequences are following:

Xaniar: $4 \rightarrow 0 \rightarrow 1 \rightarrow 2$

Abol: $0 \rightarrow 3 \rightarrow 4 \rightarrow 1$

Difficulty: competition

Starter code:

Solutions:
import fractions

def read_data():
    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())
    return m, h1, a1, x1, y1, h2, a2, x2, y2

def solve(m, h1, a1, x1, y1, h2, a2, x2, y2):
    t = 0
    h1s = [-1] * m
    h2s = [-1] * m
    h1s[h1] = 0
    h2s[h2] = 0
    t1 = -1
    t2 = -1
    while h1 != a1 or h2 != a2:
        t += 1
        h1 = (x1 * h1 + y1) % m
        h2 = (x2 * h2 + y2) % m
        if h1s[h1] >= 0 and t1 == -1:
            t1 = h1s[h1]
            s1 = t - t1
            if t2 >= 0:
                break
        else:
            h1s[h1] = t
        if h2s[h2] >= 0 and t2 == -1:
            t2 = h2s[h2]
            s2 = t - t2
            if t1 >= 0:
                break
        else:
            h2s[h2] = t
    if h1 == a1 and h2 == a2:
        return t
    return retrieve(a1, a2, t1, s1, t2, s2, h1s, h2s)

def retrieve(a1, a2, t1, s1, t2, s2, h1s, h2s):
    u1 = h1s[a1]
    u2 = h2s[a2]
    if u1 == -1 or u2 == -1:
        return -1
    if u1 < t1:
        if guess(h2s, u1, t2, s2, a2):
            return u1
        else:
            return -1
    if u2 < t2:
        if guess(h1s, u2, t1, s1, a1):
            return u2
        else:
            return -1
    return find_time(u1, s1, u2, s2)

def guess(hs, u, t, s, a):
    if u <= t:
        return hs[a] == u
    tt = t + (u - t) % s
    return hs[a] == tt

def find_time(u1, s1, u2, s2):
    g = fractions.gcd(s1, s2)
    if abs(u1 - u2) % g:
        return -1
    k1, k2 = extended_euclid(s1, s2, u2-u1, g)
    b = s2 // g
    return (k1 % b) * s1 + u1

def egcd(a, b):
    x, lastx = 0, 1
    y, lasty = 1, 0
    while b:
        q = a // b
        a, b = b, a % b
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y
    return lastx, lasty

def extended_euclid(a, b, c, g):
    x, y = egcd(a, b)
    return (c // g) * x, (x // g) * y


param = read_data()
print(solve(*param))

mod = 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())

q1 = 0
while h1 != a1:
    h1 = (h1 * x1 + y1) % mod
    q1 += 1
    if q1 > 2 * mod:
        print(-1)
        return

q2 = 0
t2 = h2
while t2 != a2:
    t2 = (t2 * x2 + y2) % mod
    q2 += 1
    if q2 > 2 * mod:
        print(-1)
        return

if q1 == q2:
    print(q1)
    return


c1 = 1
h1 = (a1 * x1 + y1) % mod
while h1 != a1:
    h1 = (h1 * x1 + y1) % mod
    c1 += 1
    if c1 > 2 * mod:
        print(-1)
        return

c2 = 0
nx2 = 1
ny2 = 0

for i in range(c1):
    nx2 = (nx2 * x2) % mod
    ny2 = (ny2 * x2 + y2) % mod

for i in range(q1):
    h2 = (h2 * x2 + y2) % mod

while h2 != a2:
    h2 = (h2 * nx2 + ny2) % mod
    c2 += 1
    if c2 > 2 * mod:
        print(-1)
        return

print(q1 + c1 * c2)

__author__ = 'kitkat'
import sys



def GetNext(h, x, y):
    nonlocal m
    return (x * h + y) % m
try:
    while True:
        m = int(input())
        h1, a1 = list(map(int, input().split(" ")))
        x1, y1 = list(map(int, input().split(" ")))
        h2, a2 = list(map(int, input().split(" ")))
        x2, y2 = list(map(int, input().split(" ")))
        t1 = []
        t2 = []
        T = 0
        for i in range (2 * m + 1):
            if h1 == a1:
                t1.append(T)
            if h2 == a2:
                t2.append(T)
            T += 1
            h1 = GetNext(h1, x1, y1)
            h2 = GetNext(h2, x2, y2)

        if len(t1) == 0 or len(t2) == 0:
            print("-1")
            continue
        if t1[0] == t2[0]:
            print(t1[0])
            continue
        elif len(t1) < 2 or len(t2) < 2:
            if len(t1) == 1 and len(t2) == 1:
                print(t1[0] if t1[0] == t2[0] else "-1")
            elif len(t1) == 1:
                if t1[0] in t2:
                    print(t1[0])
                else:
                    print("-1")
            elif len(t2) == 1:
                if t2[0] in t1:
                    print(t2[0])
                else:
                    print("-1")
            continue
        res1 = t1[0]
        res2 = t2[0]
        flag = False
        for i in range (5000000):
            if res1 == res2:
                flag = True
                print(res1)
                break
            elif res1 <= res2:
                res1 += t1[1] - t1[0]
            else:
                res2 += t2[1] - t2[0]
        if not flag:
            print("-1")
except EOFError:
    pass


def main():
    m, tt = int(input()), [0] * 4
    for i in 0, 2:
        h, a = list(map(int, input().split()))
        x, y = list(map(int, input().split()))
        ha = (h, a)
        for t in range(1, m * 2):
            h = (h * x + y) % m
            if h in ha:
                if h == ha[0]:
                    if tt[i]:
                        tt[i] = t - tt[i]
                        break
                    else:
                        tt[i] = t
                else:
                    if tt[i + 1]:
                        tt[i] = t - tt[i + 1]
                        break
                    else:
                        tt[i + 1] = t
    step1, shift1, step2, shift2 = tt if tt[0] > tt[2] else tt[2:] + tt[:2]
    if shift1 == shift2 != 0:
        print(shift1)
        return
    if step1 and not step2 and shift1 and shift1 <= shift2 and not (shift2 - shift1) % step1:
        print(shift2)
        return
    if all(tt):
        if step2 == 1:
            print(shift1 if shift1 >= shift2 else shift2 + (shift2 - shift1) % step1)
            return
        for t in range(shift1 - shift2, shift1 - shift2 + step1 * step2, step1):
            if not t % step2:
                print(t + shift2)
                return
    print(-1)


def __starting_point():
    main()

__starting_point()

mod = 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())

q1 = 0
while h1 != a1:
    h1 = (h1 * x1 + y1) % mod
    q1 += 1
    if q1 > 2 * mod:
        print(-1)
        return

q2 = 0
t2 = h2
while t2 != a2:
    t2 = (t2 * x2 + y2) % mod
    q2 += 1
    if q2 > 2 * mod:
        print(-1)
        return

if q1 == q2:
    print(q1)
    return


c1 = 1
h1 = (a1 * x1 + y1) % mod
while h1 != a1:
    h1 = (h1 * x1 + y1) % mod
    c1 += 1
    if c1 > 2 * mod:
        print(-1)
        return

c2 = 0
nx2 = 1
ny2 = 0

for i in range(c1):
    nx2 = (nx2 * x2) % mod
    ny2 = (ny2 * x2 + y2) % mod

for i in range(q1):
    h2 = (h2 * x2 + y2) % mod

while h2 != a2:
    h2 = (h2 * nx2 + ny2) % mod
    c2 += 1
    if c2 > 2 * mod:
        print(-1)
        return

print(q1 + c1 * c2)

from fractions import *
f = lambda: map(int, input().split())
m = int(input())

def g(u, v):
    h, a = u
    x, y = v

    s = 0
    while h != a:
        h = (h * x + y) % m
        s += 1
        if s > m: break

    h = (a * x + y) % m
    d = 1
    while h != a:
        h = (h * x + y) % m
        d += 1
        if d > m: break

    return s, d

(u, x), (v, y) = g(f(), f()), g(f(), f())

if u > m or v > m: q = -1
elif u == v: q = u
elif x > m: q = -1 if u < v or (v - u) % y else u
elif y > m: q = -1 if v < u or (v - u) % x else v
elif (v - u) % gcd(x, y): q = -1
else:
    while u != v:
        if u < v: u += x
        else: v += y
    q = u

print(q)