#include <stdio.h>
#include <stdint.h>

#define MODULO 2000000000

// avem ecuatia A * x + N * y = 1
uint64_t invers_modular(uint64_t A, uint64_t N, uint64_t *x, uint64_t *y)
{
    if (N == 0){   //in cazul asta avem A * 1 + 0 = A
        *x = 1;
        *y = 0;
        return A; 
    }

    uint64_t x_aux, y_aux;
    uint64_t res = invers_modular(N, A % N, &x_aux, &y_aux);

    *x = y_aux;  
    *y = x_aux - (A / N) * y_aux;

    return res;
}

int main(void)
{
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");

    uint64_t A;
    uint64_t N;
    fscanf(fin, "%lu %lu", &A, &N);

    uint64_t x, y;

    A = 5;
    N = 7;

    uint64_t res = invers_modular(A, N, &x, &y);
    // printf("%lu.\n", x);

    if (res != 1){
        // printf("inversu modular este = %lu", x);
        fprintf(fout, "%lu", x);
    }
    else{
        //prelucram.
        x = ((x % N + N) % N);
        // printf("%lu\n", x);
        fprintf(fout, "%lu", x);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}