#![allow(non_snake_case)]
use std::{fs::File, io::BufWriter};
use std::io::prelude::*;

fn modinv(a: i64, n: i64) -> i64 {
    let mut a: i64 = a;
    let mut n = n;
    let mut s0 = 1i64;
    // let mut t0 = 0i64;
    let mut s1 = 0i64;
    // let mut t1 = 1i64;
    while n > 0 {
        let q: i64 = a / n;
        let aa = n;
        n = a % n;
        a = aa;
        let ss = s1;
        s1 = s0 - s1 * q;
        s0 = ss;
    }
    s0
}
fn main() {
    let mut writer = BufWriter::new(File::create("inversmodular.out").unwrap());
    let line = std::fs::read_to_string("inversmodular.in").unwrap();
    let (A, N) = line.trim().split_once(' ').unwrap();
    let A = A.parse::<i64>().unwrap();
    let N = N.parse::<i64>().unwrap();
    let m = modinv(A, N);
    write!(writer, "{m}").expect("could not write to file");
}