#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,r;
int exprap(int x,int p)
{
    if(p==1)return x;
    if(p==0)return 1;
    if(p%2==1)return (x*exprap(x,p-1));
    int t=exprap(x,p/2);
    return t*t;
}
int phi(int n)
{
    int d=2,res=1,p;
    while(d*d<=n)
    {
        if(n%d==0)
        {
         p=0;
         while(n%d==0)
         {
             p++;
             n/=d;
         }
         res=res*(p-1)/p;
        }
        d++;
    }
    if(n!=1)res=n-1;
    return res;
}
signed main()
{
    fin>>a>>r;
    fout<<exprap(a,phi(r)-1)%r;
    return 0;
}