#include <iostream>
#include<fstream>
#include<math.h>
using namespace std;
bool prim(int n){
    if(n==0 or n==1) return 0;
    if(n!=2 && n%2==0) return 0;
    for(int i=3;i<=sqrt(n);i+=2){
        if(n%i==0) return 0;
    }
    return 1;
}
long long int exponentiererapida(int a,int n,int mod){
    long long int p=1;
    while(n>0){
        if(n%2==0){
            a=(a*a)%mod;
            n=n/2;
        }
        else{
            p=(p*a)%mod;
            n=n-1;
        }
    }
    return p%mod;
}
struct div1{
    int baza;
    int exp;
};
div1 v[1000];
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    int a,n;
    f>>a>>n;
    if(prim(n)){
        g<<exponentiererapida(a,n-2,n);
    }
    else{
        int d=2;
        int limita=0;
        int copi3=n;
        while(n>1){
            int p=0;
            if(n%d==0){
                ++limita;
                v[limita].baza=d;
            }
            while(n%d==0){
                n/=d;
                ++p;
            }
            if(p!=0){
                v[limita].exp=p;
            }
            ++d;
        }
        n=copi3;
        unsigned long long int pfi=1;
        for(int i=1;i<=limita;++i){
            pfi=pfi*(exponentiererapida(v[i].baza,v[i].exp,2000000000)-exponentiererapida(v[i].baza,v[i].exp-1,2000000000));
        }
        g<<exponentiererapida(a,pfi-1,2000000000)%n;
    }
    return 0;
}