#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;
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)%b;
        c*=c;
        c%=b;
    }
    return rez%b;
}
int main ()
{
    fin >> a >> b;
    for(i = 2; i*i < b; i++)
    {
        if(b%i == 0)
            c+=2;
    }
    if(b%i == 0)
        c++;
    b-=c;
    b--;
    b--;
    fout << exp(a,b);
    return 0;
}