use std::io::Read; fn mod_pow(r: u64, mut n: u64, p: u64) -> u64 { assert!(r < p); let mut t = 1; let mut s = r; while n > 0 { if n & 1 == 1 { t = t * s % p; } s = s * s % p; n >>= 1; } t } fn inv(a: u64, p: u64) -> u64 { assert!(0 < a && a < p); mod_pow(a, p - 2, p) } fn log(x: u64, a: u64, p: u64) -> u64 { assert!(x < p && a < p); if x == 0 { return if a == 0 {0} else {p}; } let sq = (p as f64).sqrt() as u64 + 1; let mut map = std::collections::HashMap::new(); for i in (0..sq).rev() { map.insert(a * mod_pow(inv(x, p), i, p), i); } let mut k = 1; let x = mod_pow(x, sq, p); let mut ans = p; for i in 0..sq { if let Some(&v) = map.get(&k) { ans = std::cmp::min(ans, (i * sq + v) % (p - 1)); } k = k * x % p; } return ans; } type M = [[u64; 2]; 2]; fn matmul(a: &M, b: &M, p: u64) -> M { let mut c = [[0; 2]; 2]; for (c, a) in c.iter_mut().zip(a.iter()) { for (a, b) in a.iter().zip(b.iter()) { for (c, b) in c.iter_mut().zip(b.iter()) { *c = (*c + *a * *b) % p; } } } c } fn matmul_s(a: &M, x: u64, p: u64) -> M { let mut c = [[0; 2]; 2]; for (c, a) in c.iter_mut().zip(a.iter()) { for (c, a) in c.iter_mut().zip(a.iter()) { *c = *a * x % p; } } c } fn mat_pow(a: &M, mut n: u64, p: u64) -> M { let mut t = [[0; 2]; 2]; t[0][0] = 1; t[1][1] = 1; let mut s = a.clone(); while n > 0 { if n & 1 == 1 { t = matmul(&t, &s, p); } s = matmul(&s, &s, p); n >>= 1; } t } fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let p: u64 = it.next().unwrap().parse().unwrap(); let mut a: M = [[0; 2]; 2]; let mut b: M = [[0; 2]; 2]; for i in 0..2 { for j in 0..2 { a[i][j] = it.next().unwrap().parse().unwrap(); } } for i in 0..2 { for j in 0..2 { b[i][j] = it.next().unwrap().parse().unwrap(); } } if a == b { println!("1"); return; } let det = (a[0][0] * a[1][1] + p * p - a[0][1] * a[1][0]) % p; if det == 0 { let x = (a[0][0] + a[1][1]) % p; let mut y = p; for i in 0..2 { for j in 0..2 { if a[i][j] != 0 { y = std::cmp::min(y, log(x, a[i][j], p)); } } } if y < p && b == matmul_s(&a, y, p) { println!("{}", y); } else { println!("-1"); } } else { let idet = inv(det, p); let ia = matmul_s(&[[a[1][1], (p - a[0][1]) % p], [(p - a[1][0]) % p, a[0][0]]], idet, p); assert!(matmul(&a, &ia, p) == [[1, 0], [0, 1]]); let sq = 3_000_000; let mut map = std::collections::HashMap::new(); let mut v = matmul(&b, &mat_pow(&ia, sq - 1, p), p); for i in (0..sq).rev() { map.insert(v, i); // println!("[[{}, {}], [{}, {}]]", v[0][0], v[0][1], v[1][0], v[1][1]); v = matmul(&v, &a, p); } let mut k = [[1, 0], [0, 1]]; let x = mat_pow(&a, sq, p); let mut ans = sq * sq; for i in 0..sq { if let Some(&v) = map.get(&k) { ans = std::cmp::min(ans, sq * i + v); } k = matmul(&k, &x, p); } if ans < sq * sq { println!("{}", ans); } else { println!("-1"); } } } fn main() { run(); }