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 math
def calc(crt, tgt, x, y, m):
    ttime = None
    b = [False for _ in range(m)]
    t = 0
    while True:
        b[crt] = True
        crt = (crt * x + y) % m
        t += 1
        if crt == tgt:
            ttime = t
        if b[crt]==True:
            return (t, ttime)

def ext(a,b):
    if b==1: return (0,1,1)
    r = a%b
    k = int(a/b)
    if r==0: return (0,1,b)
    x,y,g = ext(b,r)
    return (y,x-k*y,g)
    
def main():
    m = int(input())
    items = input().split()
    h1 = int(items[0])
    a1 = int(items[1])
    items = input().split()
    x1 = int(items[0])
    y1 = int(items[1])
    items = input().split()
    h2 = int(items[0])
    a2 = int(items[1])
    items = input().split()
    x2 = int(items[0])
    y2 = int(items[1])
    
    r1, t1 = calc(h1, a1, x1, y1, m)
    r2, t2 = calc(h2, a2, x2, y2, m)
    if t1==None or t2 == None:
        print(-1)
    elif t1==t2:
        print(t1)
    elif r1==r2:
        print(-1)
    else:#r1!=r2 t1 t2 valid, t1 != t2
        com = min(t1, t2)
        t1 -= com
        t2 -= com
        te = max(t1,t2)
        x,y,g = ext(r1, r2)
        if t1==0:
            if t2%g != 0:
                print(-1)
                return
            tk = int(t2/g)
            x %= r2
            tot = (x*r1*tk+com)%(int(r1*r2/g))
        else:
            if t1%g != 0:
                print(-1)
                return
            tk = int(t1/g)
            y %= r1
            tot = (y*r2*tk+com)%(int(r1*r2/g))
        print(tot)
        
if __name__ == '__main__':
    main()
    