#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
unsigned long long a, n;
unsigned long long rez=n,d=2;
long long phi(long long n)
{
    while (n>1)
    {
        if (n%d==0)
        {
            rez=rez/d*(d-1);
            while(n%d==0)n/=d;
        }
        d++;
        if (d*d>n)d=n;
    }
    return rez;
}
long long exp (long long a, long long b)
{
    long long p=1;
    while (b)
    {
        if(b%2==1)
        {
            p*=a;
            p%=n;
        }
        a*=a;
        a%=n;
        b/=2;
    }
    return p;
}

int main() {
    f>>a >>n;
    g<<exp(a,phi(n)-1)%n;
}