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

void inv_mod(long long a, long long n, long long *x, long long *y)
{
    if(n==0)
    {
        *x=1;
        *y=0;
    }
    else
    {
        long long x1, y1;
        inv_mod(n, a % n, &x1, &y1);
        *x = y1;
        *y = x1 - (a / n) * y1;
    }
}

int main(void)
{
    FILE* f,*g;
    long long A,N,x=0,y=0;
    if((f=fopen("inversmodular.in","r"))==NULL)
    {
        printf("fisierul de intrare nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if((g=fopen("inversmodular.out","w"))==NULL)
    {
        printf("fisierul de iesire nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if(fscanf(f,"%lld %lld",&A, &N)!=2)
    {
        printf("citire din fisier nereusita\n");
        exit(EXIT_FAILURE);
    }
    inv_mod(A,N,&x,&y);
    while(x < 0)
        x=(x%N+N)%N;
    fprintf(g,"%lld\n", x);
    if(fclose(f)<0)
    {
        printf("fisierul de intrare nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    if(fclose(g)<0)
    {
        printf("fisierul de iesire nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    return 0;
}