//O(log(n))
#include <stdio.h>

void euclid(int a, int b, int *x, int *y){
  if(b == 0){
    *x = 1;
    *y = 0;
    return ;
  }
  int x1, y1;
  euclid(b, a % b, &x1, &y1);
  *x = y1;
  *y = x1 - (a / b) * y1;
}

int main()
{
    FILE *in = fopen( "inversmodular.in", "r" );
    int n, m;
    fscanf( in, "%d%d", &n, &m );
    fclose( in );
    FILE *out = fopen( "inversmodular.out", "w" );
    int x, y;
    euclid(n, m, &x, &y);
    x = (1LL * x + m) % m;
    fprintf( out, "%d", x );
    fclose( out );
    return 0;
}