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<Long> toList() {
			List<Long> list = new ArrayList<Long>();
			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<Long, Integer> 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<List<Long>, 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));
	}

}