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>.
import itertools

def euclid_algorithm(a, b):
    t1, t2 = abs(a), abs(b)
    #saving equalities:
    #t1 == x1 * a + y1 * b,
    #t2 == x2 * a + y2 * b. 
    x1, y1, x2, y2 = int(math.copysign(1, a)), 0, 0, int(math.copysign(1, b))
    if t1 < t2:
        t1, t2 = t2, t1
        x1, y1, x2, y2 = x2, y2, x1, y1

    while t2 > 0:
        if x1 * a + y1 * b != t1:
            print('inshalla')
        k = int(t1 // t2)
        t1, t2 = t2, t1 % t2
        #t1 - k * t2 == (x1 - k * x2) * a + (y1 - k * y2) * b
        x1, y1, x2, y2 = x2, y2, x1 - k * x2, y1 - k * y2

    return t1, x1, y1

m = int(input())
h1, a1 = [int(x) for x in input().split()]
x1, y1 = [int(x) for x in input().split()]
h2, a2 = [int(x) for x in input().split()]
x2, y2 = [int(x) for x in input().split()]

def solve(m,h1,a1,x1,y1,h2,a2,x2,y2):
    for i in range(m):
        h1 = (x1*h1 + y1) %m
        if h1 == a1:
            k1 = i+1
            for j in range(m):
                h1 = (x1*h1 + y1) %m
                if h1 == a1:
                    period1 = j+1
                    break
            else:
                period1 = 0
            break
    else:
        return -1

    for i in range(m):
        h2 = (x2*h2 + y2) %m
        if h2 == a2:
            k2 = i+1
            for j in range(m):
                h2 = (x2*h2 + y2) %m
                if h2 == a2:
                    period2 = j+1
                    break
            else:
                period2 = 0
            break
    else:
        return -1

    if k1 == k2:
        return k1
    elif period1 == 0 and period2 == 0:
        return -1
    else:
        gcd, l1, l2 = euclid_algorithm(period1, -period2)
        if (k2 - k1)%gcd : return -1
        l1 *= (k2 - k1)//gcd 
        l2 *= (k2 - k1)//gcd #now l1*period1 + k1 == l2*period2 + k2
        while l1 < 0 or l2 < 0:
            l1 += period2//gcd
            l2 += period1//gcd
        return l1*period1 + k1

print(solve(m,h1,a1,x1,y1,h2,a2,x2,y2))



