#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

bool IsPrime [2000002];
vector <int> prnr;

void Ciur(){
    IsPrime[0] = 0;
    IsPrime[1] = 0;
    for (int i=2;i<=2000000;++i){
        IsPrime[i] = 1;
    }
    for (int i=2;i<=2000000;++i){
        if (IsPrime[i]==1){
            for (int j=2*i;j<=2000000;j+=i){
                IsPrime[j] = 0;
            }
        }
    }
    for (int i=1;i<=2000000;++i){
        if (IsPrime[i]) prnr.push_back(i);
    }
    return;
}

int Putere(int p,int e,int MOD){
    int ans = 1;
    while (e){
        if (e%2==1){
            ans = (ans*p)%MOD;
        }
        p = (p*p)%MOD;
        e = (e/2)%MOD;
    }
    return ans;
}

int Indicatorul_Lui_Euler(int n){
    int ans = n;
    for (auto f:prnr){
        if (n%f!=0) continue;
        ans = ans/f;
        ans = ans*(f-1);
    }
    return ans;
}

signed main()
{
    Ciur();
    int A,MOD;
    fin >> A >> MOD;
    fout << Putere(A,Indicatorul_Lui_Euler(MOD)-1,MOD);
    return 0;
}