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

#define lung long long
#define inpath "inversmodular.in"
#define outpath "inversmodular.out"

void rezolvare(lung *x, lung *y, lung a, lung b)
{
	if (!b)
	{
		*x=1;
		*y=0;
	}
	else
	{
		lung x0, y0;

		rezolvare(&x0, &y0, b, a%b);
        
		*x=y0;
		*y=x0-(a/b)*y0;
	}
}

int main()
{
    FILE *in = NULL, *out = NULL;

    if( (in = fopen(inpath, "r")) == NULL )
    {
        printf("Eroare la deschiderea fisierului %s.\n", inpath);
        exit(EXIT_FAILURE);
    }

    if( (out = fopen(outpath, "w")) == NULL )
    {
        printf("Eroare la deschiderea fisierului %s.\n", outpath);
        exit(EXIT_FAILURE);
    }

    lung a = 0, n = 0, inv = 0, ins = 0;

    if( fscanf(in, "%lld %lld", &a, &n) != 2 )
    {
        printf("Eroare la citirea din fisierul %s.\n", inpath);
        exit(EXIT_FAILURE);
    }
    
    rezolvare(&inv, &ins, a, n);

	if (inv < 0)
    {
		inv=n + inv % n;
    }

    fprintf(out, "%lld\n", inv);

    if( fclose(in) != 0 )
    {
        printf("Eroare la inchiderea fisierului %s.\n", inpath);
        exit(EXIT_FAILURE);
    }

    if( fclose(out) != 0 )
    {
        printf("Eroare la inchiderea fisierului %s.\n", outpath);
        exit(EXIT_FAILURE);
    }

    return 0;
}