#include <stdio.h>
#define longLong long long

int number, modulus;

void computeExtendedGCD(longLong &inverseCandidate, longLong &unused, int a, int b) {
    if (b == 0) {
        inverseCandidate = 1;
        unused = 0;
    } else {
        computeExtendedGCD(inverseCandidate, unused, b, a % b);
        longLong temp = inverseCandidate;
        inverseCandidate = unused;
        unused = temp - unused * (a / b);
    }
}

int main() {
    longLong modularInverse = 0, tempValue;

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

    scanf("%d %d", &number, &modulus);

    computeExtendedGCD(modularInverse, tempValue, number, modulus);

    if (modularInverse <= 0) {
        modularInverse = modulus + modularInverse % modulus;
    }

    printf("%lld\n", modularInverse);

    return 0;
}