#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a,n;
long long lgput(long long a, long long b)
{
    long long p = 1;
    while(b)
    {
        if(b%2==0)
        {
            b/=2;
            a = 1LL*a*a%n;
        }
        else
        {
            --b;
            p = 1LL*p*a%n;
        }
    }
    return p;
}
long long put(int a, int b)
{
    int rez = 1;
    for(int i=1;i<=b;i++)
    {
        rez*=a;
    }
    return rez;
}
int phi(int x)
{
    int d = 2;
    int rez = 1;
    while(x!=1 && d*d<=x)
    {
        int p = 0;
        while(x%d==0)
        {
            x/=d;
            ++p;
        }
        if(p)
        {
            rez = 1LL*rez*(put(d,p)-put(d,p-1));
        }
        ++d;
    }
    if(x!=1)
    {
        rez = 1LL*rez*(put(x,1)-put(x,0));
    }
    return rez;
}
int main()
{
    f>>a>>n;
    g<<lgput(a,phi(n)-1)<<'\n';
    return 0;
}