#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n,x;
int main()
{
    fin>>a>>n;
    int put=n,nr=n;
    for(int i=2;i*i<=nr;i++)
    {
        if(nr%i==0)
        {
            while(nr%i==0)
                nr/=i;
            put=(put/i)*(i-1);
        }
    }
    if(nr!=1)
        put=(put/nr)*(nr-1);
    put--;
    x=1;
    for(int p=1;p<=put;p<<=1)
    {
        if(p&put)
            x=(x*a)%n;
        a=(a*a)%n;
    }
    fout<<x;
    return 0;
}