import java.io.*; import java.util.*; class Main { public static void main(String[] args) { new Main().run(); } long MOD; class K {// quadratic field long a, b, base; public K(long a, long b, long base) { this.a = (a % MOD + MOD) % MOD; this.b = (b % MOD + MOD) % MOD; this.base = (base % MOD + MOD) % MOD; } K add(K o) { return new K((a + o.a) % MOD, (b + o.b) % MOD, base); } K sub(K o) { return new K((a - o.a + MOD) % MOD, (b - o.b + MOD) % MOD, base); } K mul(K o) { return new K((a * o.a + b * o.b * base % MOD) % MOD, (a * o.b + o.a * b) % MOD, base); } // (a+b√w)/(c+d√w)=(a+b√w)(c-d√w)/(cc-ddw) K div(K o) { long det = o.det(); K ret = this.mul(new K(o.a, -o.b, base)); ret.a = ret.a * inv(det, MOD) % MOD; ret.b = ret.b * inv(det, MOD) % MOD; return ret; } K rev() { return new K(1, 0, base).div(this); } long det() { return (a * a % MOD - b * b % MOD * base % MOD + MOD) % MOD; } boolean equiv(K o) { return a == o.a && b == o.b; } List toList() { List list = new ArrayList(); list.add(a); list.add(b); return list; } } long[][] pow(long[][] a, long n) { long[][] ret = new long[2][2]; ret[0][0] = ret[1][1] = 1; for (; n > 0; n >>= 1, a = mul(a, a)) { if (n % 2 == 1) ret = mul(ret, a); } return ret; } K[][] mul(K coe, K[][] a) { K[][] ret = new K[a.length][a[0].length]; for (int i = 0; i < a.length; ++i) for (int j = 0; j < a[i].length; ++j) ret[i][j] = a[i][j].mul(coe); return ret; } long[][] mul(long[][] a, long[][] b) { long[][] ret = new long[a.length][b[0].length]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < b[i].length; ++j) { for (int k = 0; k < a[i].length; ++k) { ret[i][j] += a[i][k] * b[k][j] % MOD; ret[i][j] = (ret[i][j] % MOD + MOD) % MOD; } } } return ret; } K[][] mul(K[][] a, K[][] b) { K[][] ret = new K[a.length][b[0].length]; for (int i = 0; i < ret.length; ++i) { for (int j = 0; j < ret[i].length; ++j) { ret[i][j] = new K(0, 0, a[0][0].base); } } for (int i = 0; i < a.length; ++i) { for (int j = 0; j < b[i].length; ++j) { for (int k = 0; k < a[i].length; ++k) { ret[i][j] = ret[i][j].add(a[i][k].mul(b[k][j])); } } } return ret; } long det(long[][] a) { return (a[0][0] * a[1][1] % MOD - a[0][1] * a[1][0] % MOD + MOD) % MOD; } K det(K[][] a) { return (a[0][0].mul(a[1][1])).sub(a[0][1].mul(a[1][0])); } long[][] rndmat(long p) { long[][] ret = new long[2][2]; Random rnd = new Random(); for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) ret[i][j] = rnd.nextInt((int) 5) % MOD; return ret; } void run() { // long p = (long) 5; // MOD = p; // for (int i = 0; i < 10000; ++i) { // long[][] a = rndmat(p); // long[][] b = rndmat(p); // long ans0 = exact(a, b, p); // long ans1 = solve(a, b, p); // if (ans0 != ans1) { // tr(a, b); // System.err.println("exact=" + ans0); // System.err.println("fast =" + ans1); // throw new AssertionError(); // } // } Scanner sc = new Scanner(System.in); long p = sc.nextLong(); long[][] a = new long[2][2]; long[][] b = new long[2][2]; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) a[i][j] = sc.nextLong(); for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) b[i][j] = sc.nextLong(); // System.out.println(exact(a, b, p)); System.out.println(solve(a, b, p)); } long solve2(long[][] a, long[][] b, long p) { if (equiv(a, b)) return 1; if (p == 2) return exact(a, b, p); Scanner sc = new Scanner(System.in); MOD = p; long w = (a[0][0] * a[0][0] % MOD - 2 * a[0][0] * a[1][1] % MOD + a[1][1] * a[1][1] % MOD + 4 * a[0][1] * a[1][0] % MOD) % MOD; K eigen1 = new K(inv(2, MOD) * (a[0][0] + a[1][1]) % MOD, -inv(2, MOD), w); K eigen2 = new K(inv(2, MOD) * (a[0][0] + a[1][1]) % MOD, inv(2, MOD), w); K[][] S = new K[2][2]; K[][] J = new K[2][2]; K[][] eigenvec1 = new K[2][1]; K[][] eigenvec2 = new K[2][1]; K[][] ak = new K[][] { { new K(a[0][0], 0, w), new K(a[0][1], 0, w) }, { new K(a[1][0], 0, w), new K(a[1][1], 0, w) } }; K[][] bk = new K[][] { { new K(b[0][0], 0, w), new K(b[0][1], 0, w) }, { new K(b[1][0], 0, w), new K(b[1][1], 0, w) } }; if (!eigen1.equiv(eigen2)) { eigenvec1 = eigenvec(ak, eigen1); eigenvec2 = eigenvec(ak, eigen2); S = new K[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } }; J = new K[][] { { eigen1, new K(0, 0, w) }, { new K(0, 0, w), eigen2 } }; if (!equiv(mul(ak, eigenvec1), mul(eigen1, eigenvec1)) || !equiv(mul(ak, eigenvec2), mul(eigen2, eigenvec2))) { tr(ak, eigenvec1, eigen1, MOD, mul(ak, eigenvec1), mul(eigen1, eigenvec1)); tr(ak, eigenvec2, eigen2, MOD, mul(ak, eigenvec2), mul(eigen2, eigenvec2)); throw new AssertionError(); } } else { throw new AssertionError(); } bk = mul(invmat(S), mul(bk, S)); if (!bk[0][1].equiv(new K(0, 0, w)) || !bk[1][0].equiv(new K(0, 0, w))) { return -1; } long sol1 = discretelog(J[0][0], bk[0][0]); long sol2 = discretelog(J[1][1], bk[1][1]); if (sol1 == -1 || sol2 == -1) return -1; long ord1 = ord(J[0][0], MOD); long ord2 = ord(J[1][1], MOD); long ans1 = sol1; long ans2 = sol2; if (Math.abs(ans1 - ans2) % gcd(ord1, ord2) != 0) return -1; while (ans1 != ans2) { if (ans1 < ans2) { ans1 += (ans2 - ans1 + ord1 - 1) / ord1 * ord1; } else { ans2 += (ans1 - ans2 + ord2 - 1) / ord2 * ord2; } } while (!equiv(pow(J, ans1), bk)) { ans1 += lcm(ord1, ord2); ans2 += lcm(ord1, ord2); } return ans1; } long solve(long[][] a, long[][] b, long p) { if (equiv(a, b)) return 1; else if (a[0][0] == 0 && a[0][1] == 0 && a[1][0] == 0 && a[1][1] == 0) return -1; else if (a[0][0] == a[1][1] && a[0][0] != 0 && a[0][1] == 0 && a[1][0] == 0) { if (b[0][0] == b[1][1] && b[0][0] != 0 && b[0][1] == 0 && b[1][0] == 0) { return discretelog(a[0][0], b[0][0]); } else { return -1; } } if (p == 2) return exact(a, b, p); Scanner sc = new Scanner(System.in); MOD = p; System.err.println("p=" + p); System.err.println("r=" + rank(a)); System.err.println("a=" + a[0][0] + " " + a[0][1]); System.err.println(" " + a[1][0] + " " + a[1][1]); long w = (a[0][0] * a[0][0] % MOD - 2 * a[0][0] * a[1][1] % MOD + a[1][1] * a[1][1] % MOD + 4 * a[0][1] * a[1][0] % MOD) % MOD; if (!isQuadraticResidue(w)) { System.err.println("sqrt[w] is not quadratic residue."); return solve2(a, b, p); } System.err.println("w=" + w); w = sqrt((w + MOD) % MOD, p); long det0 = det(a); long det1 = det(b); if (det0 == 0 && det1 != 0) return -1; long eigen1 = inv(2, MOD) * (MOD - w + a[0][0] + a[1][1]) % MOD; long eigen2 = inv(2, MOD) * (MOD + w + a[0][0] + a[1][1]) % MOD; System.err.println("eigen1=" + eigen1 + " eigen2=" + eigen2); if (eigen1 == 0 && eigen2 == 0) return exact(a, b, p); long[][] S = new long[2][2]; long[][] J = new long[2][2]; long[][] eigenvec1 = new long[2][1]; long[][] eigenvec2 = new long[2][1]; if (eigen1 != eigen2) { eigenvec1 = eigenvec(a, eigen1); eigenvec2 = eigenvec(a, eigen2); S = new long[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } }; J = new long[][] { { eigen1, 0 }, { 0, eigen2 } }; } else { // diagonalization is impossible. System.err.println("diagonalization is impossible."); eigenvec1 = eigenvec(a, eigen1); long[][] tmp = new long[][] { { (a[0][0] - eigen1 + MOD) % MOD, a[0][1] }, { a[1][0], (a[1][1] - eigen1 + MOD) % MOD } }; eigenvec2 = solveLinearEq(tmp, eigenvec1); S = new long[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } }; J = new long[][] { { eigen1, 1 }, { 0, eigen2 } }; } System.err.println("eigenvec1=" + eigenvec1[0][0] + " " + eigenvec1[1][0]); System.err.println("eigenvec2=" + eigenvec2[0][0] + " " + eigenvec2[1][0]); System.err.println("J=" + J[0][0] + " " + J[0][1]); System.err.println(" " + J[1][0] + " " + J[1][1]); b = mul(invmat(S), mul(b, S)); System.err.println("S^(-1)BS=" + b[0][0] + " " + b[0][1]); System.err.println(" " + b[1][0] + " " + b[1][1]); if (b[1][0] != 0 && J[1][0] == 0) { return -1; } if (eigen1 != eigen2 && eigen1 != 0 && eigen2 != 0) { if (b[0][1] != 0 || b[1][0] != 0) return -1; } if ((b[0][0] != 0 && J[0][0] == 0) || (b[1][1] != 0 && J[1][1] == 0)) return -1; if (J[0][1] == 0 && b[0][1] != 0) return -1; long sol1 = discretelog(J[0][0], b[0][0]); long sol2 = discretelog(J[1][1], b[1][1]); if (sol1 == -1 || sol2 == -1) return -1; long ord1 = ord(J[0][0], MOD); long ord2 = ord(J[1][1], MOD); long ans1 = sol1; long ans2 = sol2; if (Math.abs(ans1 - ans2) % gcd(ord1, ord2) != 0) return -1; while (ans1 != ans2) { if (ans1 < ans2) { ans1 += (ans2 - ans1 + ord1 - 1) / ord1 * ord1; } else { ans2 += (ans1 - ans2 + ord2 - 1) / ord2 * ord2; } } while (!equiv(pow(J, ans1), b)) { ans1 += lcm(ord1, ord2); ans2 += lcm(ord1, ord2); } return ans1; } boolean equiv(long[][] a, long[][] b) { boolean ret = true; if (a[0].length != b[0].length || a[1].length != b[1].length) throw new AssertionError(); for (int i = 0; i < a.length; ++i) for (int j = 0; j < a[0].length; ++j) ret &= a[i][j] == b[i][j]; return ret; } long[][] eigenvec(long[][] a, long eigenval) { long[][] tmp = new long[][] { { (a[0][0] - eigenval + MOD) % MOD, a[0][1] }, { a[1][0], (a[1][1] - eigenval + MOD) % MOD } }; if (tmp[0][0] != 0 || tmp[0][1] != 0) { return new long[][] { { (MOD - tmp[0][1]) % MOD }, { tmp[0][0] } }; } else { return new long[][] { { (MOD - tmp[1][1]) % MOD }, { tmp[1][0] } }; } } K[][] eigenvec(K[][] a, K eigenval) { long base = a[0][0].base; K[][] tmp = new K[][] { { a[0][0].sub(eigenval), a[0][1] }, { a[1][0], a[1][1].sub(eigenval) } }; if (!tmp[0][0].equiv(new K(0, 0, base)) || !tmp[0][1].equiv(new K(0, 0, base))) { return new K[][] { { new K(0, 0, base).sub(tmp[0][1]) }, { tmp[0][0] } }; } else { return new K[][] { { new K(0, 0, base).sub(tmp[1][1]) }, { tmp[1][0] } }; } } boolean equiv(K[][] a, K[][] b) { boolean ret = true; if (a[0].length != b[0].length || a[1].length != b[1].length) throw new AssertionError(); for (int i = 0; i < a.length; ++i) for (int j = 0; j < a[0].length; ++j) ret &= a[i][j].equiv(b[i][j]); return ret; } long exact(long[][] a, long[][] b, long p) { MOD = p; for (int i = 1; i < p * p; ++i) { long[][] pw_a = pow(a, i); boolean equiv = true; for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) equiv &= pw_a[j][k] == b[j][k]; if (equiv) return i; } return -1; } long inv(long a, long mod) { return pow(a, mod - 2); } long ord(long a, long p) { if (a == 0 || a == 1) return 1; long ret = p - 1; for (long div = 2; div * div <= p - 1; ++div) { if ((p - 1) % div != 0) continue; if (pow(a, div) == 1) ret = Math.min(ret, div); else if (pow(a, (p - 1) / div) == 1) ret = Math.min(ret, (p - 1) / div); } return ret; } long ord(K a, long p) { long base = a.base; if (a.equiv(new K(0, 0, base)) || a.equiv(new K(1, 0, base))) return 1; long ret = 2 * p - 1;// (a+bw)^2p=a+bw for (long div = 2; div * div <= 2 * p - 1; ++div) { if ((p - 1) % div != 0) continue; if (pow(a, div).equiv(new K(1, 0, base))) ret = Math.min(ret, div); else if (pow(a, (p - 1) / div).equiv(new K(1, 0, base))) ret = Math.min(ret, (p - 1) / div); } return ret; } long pow(long a, long n) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % MOD) { if (n % 2 == 1) ret = ret * a % MOD; } return ret; } K pow(K a, long n) { K ret = new K(1, 0, a.base); for (; n > 0; n >>= 1, a = a.mul(a)) { if (n % 2 == 1) ret = ret.mul(a); } return ret; } K[][] pow(K[][] a, long n) { K[][] ret = new K[2][2]; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { ret[i][j] = new K(i == j ? 1 : 0, 0, a[0][0].base); } } for (; n > 0; n >>= 1, a = mul(a, a)) { if (n % 2 == 1) ret = mul(ret, a); } return ret; } // return x s.t. a^x = b && x>0 long discretelog(long a, long b) { if (a == 1) { if (b == 1) return 1; else return -1; } else if (a == 0) { if (b == 0) return 1; else return -1; } // a^(um+v) = b // a^v = b a^(-m)^u int m = (int) (Math.sqrt(MOD) + 1); long pw = 1; HashMap map = new HashMap<>(); for (int v = 0; v <= m; ++v) { map.put(pw, v); pw = pw * a % MOD; } long ima = pow(inv(a, MOD), m); long ipw = 1; for (int i = 0; i <= m; ++i) { if (map.containsKey(b * ipw % MOD)) { long ret = i * m + map.get(b * ipw % MOD); if (ret != 0) return ret; } ipw = ipw * ima % MOD; } return -1; } long exact_discretelog(K a, K b) { for (int i = 1; i <= 2 * MOD * MOD - 1; ++i) { if (pow(a, i).equiv(b)) { return i; } } return -1; } // return x s.t. a^x = b && x>0 long discretelog(K a, K b) { System.err .println("discretelog " + a.a + "+" + a.b + "sqrt" + b.base + " " + b.a + "+" + b.b + "sqrt" + b.base); System.err.println("exact_discretlog " + exact_discretelog(a, b)); long base = a.base; if (a.equiv(new K(1, 0, base))) { if (b.equiv(new K(1, 0, base))) return 1; else return -1; } else if (a.equiv(new K(0, 0, base))) { if (b.equiv(new K(0, 0, base))) return 1; else return -1; } long e = discretelog(a.det(), b.det()); long ord = ord(a.det(), MOD); if (pow(a, e).equiv(b)) return e; System.err.println("det(a)=" + a.det() + " det(b)=" + b.det()); System.err.println("ord(det(a))=" + ord); System.err.println("det(a)^" + e + "=det(b)"); int m = (int) (Math.sqrt(MOD + 2)); HashMap, Integer> map = new HashMap<>(); for (int v = m - 1; v >= 0; --v) { map.put(pow(a, ord * v).toList(), v); } K ima = pow(a.rev(), ord * m); K ipw = new K(1, 0, base); for (int i = 0; i <= m; ++i) { if (map.containsKey(b.mul(ipw).mul(pow(a.rev(), e)).toList())) { long get = map.get(b.mul(ipw).mul(pow(a.rev(), e)).toList()); long ret = ord * (i * m + get) + e; if (ret != 0) { System.err.println("fast_discretlog" + ret); return ret; } } ipw = ipw.mul(ima); } return -1; } long[][] invmat(long[][] a) { if (det(a) == 0) throw new AssertionError(); long[][] ret = new long[2][2]; ret[0][0] = a[1][1]; ret[1][1] = a[0][0]; ret[0][1] = (MOD - a[0][1]) % MOD; ret[1][0] = (MOD - a[1][0]) % MOD; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) ret[i][j] = ret[i][j] * inv(det(a), MOD) % MOD; return ret; } K[][] invmat(K[][] a) { long base = a[0][0].base; if (det(a).equiv(new K(0, 0, base))) throw new AssertionError(); K[][] ret = new K[2][2]; ret[0][0] = new K(a[1][1].a, a[1][1].b, base); ret[1][1] = new K(a[0][0].a, a[0][0].b, base); ret[0][1] = new K(-a[0][1].a, -a[0][1].b, base); ret[1][0] = new K(-a[1][0].a, -a[1][0].b, base); for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) ret[i][j] = ret[i][j].mul(det(a).rev()); return ret; } long gcd(long a, long b) { if (a > b) return gcd(b, a); if (a == 0) return b; return gcd(a, b % a); } long lcm(long a, long b) { return a / gcd(a, b) * b; } long rank(long[][] a) { long[][] tmp = new long[2][2]; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) tmp[i][j] = a[i][j]; int p = 0; for (int i = 0; i < 2; ++i) { boolean find = false; for (int j = p; j < 2; ++j) { if (tmp[j][i] != 0) { if (p != j) { for (int k = 0; k < 2; ++k) { tmp[p][k] ^= tmp[j][k]; tmp[j][k] ^= tmp[p][k]; tmp[p][k] ^= tmp[j][k]; } } find = true; break; } } if (find) { for (int j = 0; j < 2; ++j) { if (p == j) continue; long pre = tmp[j][i]; for (int k = 0; k < 2; ++k) { tmp[j][k] -= tmp[p][k] * inv(tmp[p][i], MOD) % MOD * pre % MOD; tmp[j][k] = (tmp[j][k] + MOD) % MOD; } } ++p; } } return p; } long[][] solveLinearEq(long[][] A, long[][] v) { long[][] x = new long[2][1]; long[][] A_ = new long[2][2]; long[][] v_ = new long[2][1]; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) A_[i][j] = A[i][j]; for (int i = 0; i < 2; ++i) v_[i][0] = v[i][0]; int p = 0; for (int i = 0; i < 2; ++i) { boolean find = false; for (int j = p; j < 2; ++j) { if (A_[j][i] != 0) { if (p != j) { for (int k = 0; k < 2; ++k) { A_[p][k] ^= A_[j][k]; A_[j][k] ^= A_[p][k]; A_[p][k] ^= A_[j][k]; } v_[p][0] ^= v_[j][0]; v_[j][0] ^= v_[p][0]; v_[p][0] ^= v_[j][0]; } find = true; break; } } if (find) { for (int j = 0; j < 2; ++j) { if (p == j) continue; long coe = A_[j][i]; long normalize = inv(A_[p][i], MOD); for (int k = 0; k < 2; ++k) A_[p][k] = A_[p][k] * normalize % MOD; v_[p][0] = v_[p][0] * normalize % MOD; for (int k = 0; k < 2; ++k) { A_[j][k] -= A_[p][k] * coe % MOD; A_[j][k] = (A_[j][k] + MOD) % MOD; } v_[j][0] = (v_[j][0] - v_[p][0] * coe % MOD + MOD) % MOD; } x[i][0] = v_[p][0]; ++p; } } if (!equiv(mul(A, x), v)) { tr(A); tr(x); tr(v); throw new AssertionError(); } return x; } boolean isQuadraticResidue(long a) { return a == 0 || pow(a, (MOD - 1) / 2) == 1; } long sqrt(long a, long p) { if (a == 0) return 0; int b = 0; while (pow((b * b % p - a + p) % p, (p - 1) / 2) != p - 1) ++b; long[] d = { 1, 0 }; long[] m = { b, 1 }; long n = (p + 1) / 2; for (; n > 0; n >>= 1, m = poly_mul(m, m, b, a, p)) { if (n % 2 == 1) d = poly_mul(d, m, b, a, p); } return d[0]; } long[] poly_mul(long[] u, long[] v, long b, long a, long p) { long[] ret = new long[3]; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { ret[i + j] += u[i] * v[j]; ret[i + j] %= p; } } ret[0] += ret[2] * (b * b - a); ret[0] %= p; for (int i = 0; i < ret.length; ++i) { while (ret[i] < 0) ret[i] += p; } return Arrays.copyOf(ret, 2); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }