#include <bits/stdc++.h>

using namespace std;

long long N, K, rest;

long long lgput(long long x, long long n){
    if(N * x % K !=1){
        return lgput(x * (N % K), n * 2) % K;
    } else {
        return x;
    }
}

int main(){

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

    scanf("%lld%lld", &N, &K);

    printf("%lld", lgput(N % K, 1));

    return 0;
}