#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream fin ( "inversmodular.in" );
ofstream fout ( "inversmodular.out" );

void invmod( long long &x, long long &y, long long a, long long b ) {
  if ( b == 0 ) {
    x = 1;
    y = 0;
  }
  else {
    invmod( x, y, b, a % b );
    long long aux = x;
    x = y;
    y = aux - y * ( a / b );
  }
}

int main() {
  long long n, k, inv, idk;
  fin >> k >> n;
  inv = 0;
  invmod( inv, idk, k, n );
  if ( inv < 0 )
    inv += n;
  fout << inv % n;
  return 0;
}