#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n;

long long phi(long long n)
{
    long long cur=n;
    for(long long i=2;i*i<=n;i++)
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            cur=(cur/i)*(i-1);
        }
    if(n!=1)
        cur=(cur/n)*(n-1);
    return cur;
}

long long powlog(int a, int p)
{
    if(p==1)
        return a%n;
    if(p%2==0)
        return powlog((a%n*a%n)%n,p/2);
    else
        return (powlog(((a%n)*(a%n))%n,p/2)*(a%n))%n;
}

int main()
{
    fin>>a>>n;
    fout<<powlog(a,phi(n)-1);
    return 0;
}