def log_mod(a,b,MOD): a %= MOD; b %= MOD q = int(MOD**0.5)+2 # baby-step h = 1 if MOD != 1 else 0 memo = {} for i in range(q): if h==b: return i memo[h*b%MOD] = i h = h*a%MOD # giant-step #ここに来た時 h = a^q g = h for i in range(q): if g in memo: res = (i+1)*q-memo[g] if pow(a,res,MOD) == b: return res else: return -1 g = g*h%MOD return -1 #見つからない場合 def extgcd(x,y): if y==0: return 1,0 #g=x r0,r1,s0,s1 = x,y,1,0 while r1 != 0: r0,r1, s0,s1 = r1,r0%r1, s1,s0-r0//r1*s1 #g = r0 return s0,(r0-s0*x)//y def modinv(a,MOD): x,y = extgcd(a,MOD) return x%MOD def matmul(A,B,mod): # A,B: 行列 res = [[0]*len(B[0]) for _ in [None]*len(A)] for i, resi in enumerate(res): for k, aik in enumerate(A[i]): for j,bkj in enumerate(B[k]): resi[j] += aik*bkj resi[j] %= mod return res def matpow(A,p,M): #A^p mod M if p%2: return matmul(A, matpow(A,p-1,M), M) elif p > 0: b = matpow(A,p//2,M) return matmul(b,b,M) else: return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))] # coding: utf-8 # Your code here! import sys sys.setrecursionlimit(10**6) readline = sys.stdin.readline read = sys.stdin.read def hash_projective(A): c = A[0]+A[1] for i in range(4): if c[i] != 0: break else: return((4,0,0,0)) cinv = modinv(c[i],MOD) res = [i] for j in range(4): if i != j: res.append(c[j]*cinv) return tuple(res) def hash_equal(A): return tuple(A[0]+A[1]) def discrete_logarithm(a,b,MOD,hashing,permit0): q = int(MOD**0.5)+3 # baby-step h = [[1 if i == j else 0 for j in range(2)] for i in range(2)] memo = {} for i in range(q): if hashing(h)==hashing(b) and (permit0 or i): return i memo[hashing(matmul(h,b,MOD))] = i h = matmul(h,a,MOD) # giant-step #ここに来た時 h = a^q g = [i[:] for i in h] for i in range(q): if hashing(g) in memo: res = (i+1)*q-memo[hashing(g)] if matpow(a,res,MOD) == b: return res else: return -1 g = matmul(g,h,MOD) return -1 #見つからない場合 def det(A): return (A[0][0]*A[1][1]-A[1][0]*A[0][1])%MOD MOD = int(input()) A = [[int(i) for i in readline().split()] for _ in range(2)] B = [[int(i) for i in readline().split()] for _ in range(2)] if det(A) == 0: print(discrete_logarithm(A,B,MOD,hash_equal,0)) else: E = [[1 if i == j else 0 for j in range(2)] for i in range(2)] # A^ai == r E , A^bi == s B # A^(xai+bi) == B なら r^x E= (B (A^bi)^{-1}) ai = discrete_logarithm(A,E,MOD,hash_projective,0) Ar = matpow(A,ai,MOD) r = Ar[0][0] bi = discrete_logarithm(A,B,MOD,hash_projective,1) C = matpow(A,bi,MOD) dd = modinv(det(C),MOD) #print(C,B) Cinv = [[C[1][1]*dd%MOD,-C[0][1]*dd%MOD], [-C[1][0]*dd%MOD,C[0][0]*dd%MOD]] B = matmul(B,Cinv,MOD) s = B[0][0] #print(ai,bi) #print(Ar,B) # r^x = s mod P を解く x = log_mod(r,s,MOD) if x == -1: print(-1) else: print(x*ai+bi)