#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
typedef long long ll;
vector <int> prim;
bool primes[100000];
ll expo(int a,int b,int mod){
          if (b==0) return 1%mod;
          ll x=expo(a,b/2,mod);
          x=(x*x)%mod;
          if (b&1) x=(x*a)%mod;
          return x;

}

void factors(int N){
    vector <int > rs;
    for (int i=2;i*i<=N;i++){
    while (N%i==0){
        rs.push_back(i);
        N/=i;
    }

    }
    if (N>1) rs.push_back(N);
    for (auto it:rs) cout <<it <<" ";

}

bool isprime(int x){
    for (int i=2;i*i<=x;i++) if (x%i==0) return 0;
    return 1;
}

void buildprimes(){
    memset(primes,1,sizeof(primes));
    for (int i=2;i<=100000;i++){
        if (primes[i]){
                prim.push_back(i);
            for (int j=2*i;j<=100000;j+=i){
                primes[j]=0;
            }
        }

    }
    for (auto it :prim) cout <<it <<" ";
}

long long int phi(long long x)
 {
   long long int ret = 1,i,pow;
   for (i = 2; x != 1; i++)
   {
     pow = 1;
     if(i>sqrt(x))break;
     while (!(x%i))
     {
       x /= i;
       pow *= i;
     }
     ret *= (pow - (pow/i));
    }
    if(x!=1)ret*=(x-1);
    return ret;
}

long long myphi(long long x){
    vector <int > rs;
    for (int i=2;i*i<=x;i++){
    while (x%i==0){
        rs.push_back(i);
        x/=i;
    }

    }
    if (x>1) rs.push_back(x);
    long long ans=1;
    for (int i=0;i<rs.size();){
        int nr=rs[i],k=1;
        while (i+1<rs.size() && rs[i+1]==nr) i++,k++;
       // cout <<nr<<" "<<k<<endl;
        k--;
        i++;
        ans*=expo(nr,k,2000001557)*(nr-1);
    }
    return ans;
}

long long inv(long long x,long long mod){
    return expo(x,myphi(mod)-1,mod);
}

int main()
{
    long long a,b;
    fin >>a>>b;
    fout <<inv(a,b);
    return 0;
}