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

using namespace std;

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

ll a,n,mod;
bool ciur[2000005];
vector<ll> prime;

void erat()
{
    ciur[0]=1;
    ciur[1]=1;
    for(int i=2; i<200000; i++)
    {
        if(ciur[i]==0)
        {
            prime.push_back(i);
            for(int j=2*i; j<200000; j+=i)
            {
                ciur[j]=1;
            }
        }
    }
}

ll putlog(ll nr, ll p)
{
    if(p==0) return 1;
    if(p==1) return nr%mod;
    if(p%2==0) return putlog(nr*nr%mod,p/2)%mod;
    if(p%2==1) return nr*putlog(nr*nr%mod,p/2)%mod;
}

int main()
{
    fin>>a>>n;
    erat();
    ll phi=1;
    mod=n;
    for(auto x: prime)
    {
        if(n==1) break;
        if(n%x==0)
        {
            phi*=x-1;
            n/=x;
        }
        while(n%x==0)
        {
            phi*=x;
            n/=x;
        }
    }
    if(n!=1) phi*=n-1;
    fout<<putlog(a,phi-1)%mod;
    return 0;
}