#include <fstream>
#include <string.h>
#include <vector>
#include <queue>
#include <limits.h>

#define nMax 100001
#define lgMax 19
#define pb push_back
#define INF INT_MAX
#define bit(i) i&(-i)
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int n, MOD;

long long lg_power(int nr, int exp)
{
    if(exp==0)
        return 1;

    if(exp%2==0)
    {
        long long half=lg_power(nr, exp/2);
        return (half*half)%MOD;
    }

    if(exp%2==1)
        return (nr*lg_power(nr, exp-1))%MOD;
}
int main()
{
    fin>>n>>MOD;
    int phi=get_phi(n);
    fout<<lg_power(n, phi-1);
    return 0;
}