#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a,n;

int powr(int x, int y)
{
    int P=1;
    while ( y )
    {
        if ( y%2==1 )
        {
            P*=x;
            P=P%n;
        }
        x*=x;
        x=x%n;
        y/=2;
    }
    return P;
}

int euler(int n)
{
    int prod=n;
    int d=2;
    while ( n>1 )
    {
        if ( n%d==0 )
        {
            prod=prod/d*(d-1);
            while ( n%d==0 )
                n/=d;
        }
        d++;
        if ( d*d>n )
            d=n;
    }
    return prod;
}

int main()
{
    f >> a >> n;
    int k=euler(n);
    g << powr(a,k-1)%n;
    return 0;
}