#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
vector <int> prime;
bool ciur[45005];
int MOD;
void eratostene()
{
    ciur[0]=ciur[1]=1;
    for (int i=2; i<=45000; i++) {
        if (ciur[i]==0) {
            for (int j=i*i; j<=45000; j+=i) 
                ciur[j]=1;
        }
    }
    for (int i=2; i<=45000; i++) {
        if (!ciur[i])
            prime.push_back(i);
    }
}

int phi (int n)
{
    int i=0;
    int ph=n;
    while (prime[i]<=sqrt(n)) {
        //cout<<ph<<endl;
        int d=prime[i];
        if (n%d==0) {
            ph/=d;
            ph*=(d-1);
            while (n%d==0) n/=d;
        }
        i++;
    }
    //cout<<n<<' '<<ph<<endl;
    if (n!=1) {
        ph/=n;
        ph*=(n-1);
    }
    return ph;
}

ll powl (ll a, ll b)
{
    ll p=1;
    while (b) {
        if (b%2==1) {
            p*=a;
            p%=MOD;
        }
        a*=a;
        a%=MOD;
        b/=2;
    }
    return p;
}

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, a;
    fin>>n>>a;
    MOD=a;
    eratostene();
    ll indeuler=(ll)phi(a);
    //cout<<n<<' '<<indeuler<<endl;
    ll inv=powl(n, indeuler-1);
    fout<<inv;
    return 0;
}