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

using namespace std;

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

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,cn = n;
    for (int f=2;f*f<=n;++f){
        if (cn%f!=0) continue;
        while (cn%f==0) cn /= f;
        ans = ans/f;
        ans = ans*(f-1);
    }
    if (cn>1){
        ans = ans/cn;
        ans = ans*(cn-1);
    }
    return ans;
}

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