#include <bits/stdc++.h>

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]<=n) {
        int d=prime[i];
        if (n%d==0) {
            ph/=d;
            ph*=(d-1);
        }
        i++;
    }
    return ph;
}

int powl (int a, int b)
{
    int 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();
    int indeuler=phi(a);
    int inv=powl(n, indeuler-1);
    fout<<inv;
    return 0;
}