#include <stdio.h>

void hcf (int &x, int &y, int &a, int b)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    //return a;
  } // if

  else
  {
    hcf(x, y, b, a % b);
    unsigned long temp = x;
    x = y;
    y = temp - y * (a / b);
  } // while

  //return a;
} // hcf

int main()
{
    int y, p;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d %d", &y, &p);
    int inverse, temp;
    hcf(inverse, temp, y, p);
    if (inverse <= 0)
      inverse = p + inverse % p;
    printf("%d\n", inverse);
    return 0;
}