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 fractions import gcd
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(' '))

xanier = [h1]
abol = [h2]
while (x1 * xanier[-1] + y1)%m != xanier[0]:
    xanier.append((x1 * xanier[-1] + y1)%m)
    if xanier[-1] == xanier[-2]:
        break


while (x2 * abol[-1] + y2)%m != abol[0]:
    abol.append((x2 * abol[-1] + y2)%m)

    if abol[-1] == abol[-2]:
        break

if len(xanier) == 1:
    xanier.append(xanier[0])

if len(abol) == 1:
    abol.append(abol[0])

if abol[-1] == abol[-2]:
    perA = 1

else:
    perA = len(abol)
    
if xanier[-1] == xanier[-2]:
    perX = 1

else:
    perX = len(xanier)
    
if perA > 1 and perX > 1:
    iX = 0
    iA = 0
    for i in range(perX):
        if xanier[i] == a1:
            iX = i
            break

    for i in range(perA):
        if abol[i] == a2:
            iA = i

    if iX % gcd(perX, perA) != iA % gcd(perX, perA):
        print(-1)
        quit()

    else:
        for i in range(10000000):
            if (iX + perX * i)%(perA) == iA:
                print(iX + perX * i)
                quit()

if perA == 1 and perX == 1:
    if xanier[0] == a1 and abol[0] == a2:
        print(0)
    elif xanier[1] == a1 and abol[1] == a2:
        print(1)
    else:
        print(-1)

elif perA > 1 and perX == 1:
    if xanier[0] == a1 and abol[0] == a2:
        print(0)
    else:
        if xanier[1] != a1:
            print(-1)
        else:
            for i in range(perA):
                if abol[i] == a2:
                    iA = i
            if iA == 0:
                print(perA)
            else:
                print(iA)

elif perA == 1 and perX > 1:
    if abol[0] == a2 and xanier[0] == a1:
        print(0)
    else:
        if abol[1] != a2:
            print(-1)
        else:
            for i in range(perX):
                if xanier[i] == a1:
                    iX = i
            if iX == 0:
                print(perX)
            else:
                print(iX)
                
