#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int v[200][200];
long long int i,j,n,m,t,a,b,c,mod;
long long int exp(int a, int p)
{
    long long int c = a;
    long long int rez = 1;
    for(i = 1; i <= p; i*=2)
    {
        if(i&p)
            rez = (rez*c)%mod;
        c*=c;
        c%=mod;
    }
    return rez%mod;
}
int main ()
{
    fin >> a >> b;
    for(i = 2; i*i < b; i++)
    {
        if(b%i == 0)
            c+=2;
    }
    if(i*i == b)
        c++;
    mod = b;
    fout << exp(a,b-c-2);
    return 0;
}