#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))%r;
    int t=exprap(x,p/2)%r;
    return (t*t)%r;
}
int phi(int n)
{
    int d=2,res=n,p;
    while(d*d<=n)
    {
        if(n%d==0)
        {
         while(n%d==0)
         {
             n/=d;
         }
         res=(res/d)*(d-1);
        }
        d++;
    }
    if(n!=1)res=(res/n)*(n-1);
    return res;
}
signed main()
{
    fin>>a>>r;
    fout<<exprap(a,phi(r)-1)%r;
    return 0;
}