#include <iostream>
#include <stdio.h>

using namespace std;

bool prim(long long int n){
    if(n<=1)
        return false;
    for(int j=2; j*j<=n; ++j)
        if(n%j==0)
            return false;
    return true;
}

long long int putere(long long int b, long long int p, long long int mod){
    if(p==0)
        return 1;
    if(p==1)
        return b;
    if(p%2==0){
        long long int x=putere(b, p/2, mod)%mod;
        return (x%mod*x%mod)%mod;
    }
    return ((b%mod)*(putere(b, p-1, mod)%mod))%mod;
}

long long int phi(long long int n){
    if(prim(n))
        return n-1;

    long long int nr=n;
    for(long long int i=2; i*i<=n; ++i){
        if(n%i==0 && prim(i)){
            nr=nr-nr/i;
            if(n/i!=i && prim(n/i)){
                nr=nr-nr/(n/i);
            }
        }
    }
    return nr;
}

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

    long long int n, a;

    fscanf(fin, "%lld%lld", &a, &n);
    a=putere(a, phi(n)-1, n);
    fprintf(fout, "%lld", a%n);

    return 0;
}