#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define max(a,b) ((a) > (b) ? (a) : (b))  
#define toBig(a) (*new big(a))
#define CMAX 21
#define BASE 10  
          
class big {    //nr intregi mari

        public:

        int num[CMAX];
        bool sgn;

        void init(int x) {

                memset(num,0,sizeof num);
                num[0] = 1;
                sgn = 0;

                if(!x) return;
                if(x<0) sgn = 1, x = -x;
                
                int i;
                for(i = 1; x ; ++i, x/=BASE)
                 num[i] = x % BASE;
                num[0] = i - 1;
        }

        big()
        {
                init(0);
        }

        big(int v)
        {
                init(v);
        }

        big & operator= (int v) {

                init(v);
                return *this;
        }

        void get_nrdig(int best) {
             
             int * A = num;

             for(A[0] = best; !A[A[0]] && A[0] > 1 ; --A[0]);
        }

        void sgn0() {
             if(num[1] == 0 && num[0] == 1) sgn = 0;
        }

        int cmp(big &N) {

                int i, *A = num, *B = N.num;
                
                if(sgn < N.sgn) return -1;
                if(sgn > N.sgn) return 1;
                
                for(i = max(A[0],B[0]); i && A[i] == B[i]; --i);

                if(!i) return 0;
                return A[i] < B[i] ? (!sgn ? 1 : -1) : !sgn ? -1 : 1;
        }
        
        big & operator<<(int b) {
            
            memmove(num+1+b,num+1,num[0]*sizeof(int));
            memset(num+1,0,b*sizeof(int));
            get_nrdig(num[0]+b);

            return *this;
            }
        
        big & operator-() {
            
            big *res = new big; 
            memcpy(res->num,num,(num[0]+1)*sizeof(int));
            res->sgn = !sgn;
            return *res;
            }
        
        big & operator+ (big &N) {
            
              if(sgn != N.sgn) return operator-(-N);
            
                big *res = new big;
                int *A = num, *B = N.num, *C = res->num;

                int i=1,t=0;
                for(; i <= max(A[0],B[0]) || t; ++i, t/=BASE)
                 C[i] += (t+=A[i]+B[i]) % BASE;

                C[0] = i - 1;
                res->sgn = sgn; res->sgn0();
                
                return *res;
        }

        big & operator- (big &N) {
            
              if(sgn != N.sgn) return operator+(-N);
              if(sgn && N.sgn) return -N - (-(*this));
  
                big * res = new big;
                int *A = num, *B = N.num, *C = res->num;
                
                for(int i=1,t=0; i <= max(A[0],B[0]); ++i)
                 (C[i] = A[i] - B[i] - t) < 0 ? C[i] += BASE, t = 1 : t = 0;
                
                res->get_nrdig(max(A[0],B[0]));
                if(*this < N) *res = ( toBig(1) << max(A[0],B[0])) - *res, res->sgn = 1;
                
                return *res;
        }

        big & operator* (big &N) {

                big * res = new big;
                int *A = num, *B = N.num, *C = res->num;

                int i,j,t;
                for(i=1; i <= A[0] ; ++i)
                 for(j=1,t=0; j <= B[0] || t; ++j, t/=BASE)
                        C[i + j - 1] = (t += C[i + j - 1] + A[i]*B[j]) % BASE;
               
                res->get_nrdig(A[0] + B[0]);
                res->sgn = sgn ^ N.sgn; res->sgn0();
                
                return *res;
        }

        void divide(big &D2,big &Q,big &R) {

                int *a = num, *quo = Q.num, *rem = R.num;

                bool sav1 = sgn, sav2 = D2.sgn;
                sgn = D2.sgn = 0;

                int i;
                for(i = a[0]; i; --i) {
                     R = R << 1;
                     rem[1] = a[i];
                     while(R >= D2) {
                        quo[i]++;
                        R = R - D2;
                     }
                }
                
                Q.get_nrdig(a[0]);
                sgn = sav1, D2.sgn = sav2;
                Q.sgn = sgn ^ D2.sgn; Q.sgn0();
                R.sgn = sgn; R.sgn0();
        }
        
        big & operator/ (big &N) {

                big *Q = new big, *R = new big;
                if(N != toBig(0)) divide(N,*Q,*R);
                return *Q;
        }
        
        big & operator% (big &N) {

                big *Q = new big, *R = new big;
                if(N != toBig(0)) divide(N,*Q,*R);
                return *R;
        }

        inline bool operator== (big &N) {return !cmp(N);}
        inline bool operator!= (big &N) {return cmp(N);}
        inline bool operator>= (big &N) {return cmp(N) < 1;}
        inline bool operator<= (big &N) {return cmp(N) > -1;}
        inline bool operator> (big &N) {return cmp(N) == -1;}
        inline bool operator< (big &N) {return cmp(N) == 1;}
        
        void read() {
             
             char c[CMAX];
             scanf("%s",c);
             
             num[0] = 0;
             for(int i = strlen(c) - 1; i >= 0; --i)
                     if(c[i] == '-') sgn = 1;
                      else num[++num[0]] = c[i] - '0';
        }
        
        void print() {

                int *A = num;

                if(sgn) printf("-");
                for(int i=A[0];i;--i)
                        printf("%d",A[i]);
                //printf("\n");
        }
};


big ZERO(0),ONE(1),TWO(2);

void euclid(big A,big B,big &X,big &Y) {
     
     if(B == ZERO) 
          X = 1, Y = 0;
      else
      {
          euclid(B, A % B,X,Y);
          big X0 = X,Y0 = Y; 
          X = Y0;
          Y = X0 - A/B * Y0; 
          }
}

int main() {

        freopen("inversmodular.in","r",stdin);
        freopen("inversmodular.out","w",stdout);

        big A,N,res,tmp;
        A.read(); N.read();
        
        euclid(A,N,res,tmp);

        while(res < ZERO) res = res + N;
        
        res.print();
        
        return 0;
}