#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int a,b,mod;

inline int Lgput(int x,int n)
{
    int s=1;
    while(n>0)
    {
        if(n%2==1)s=1LL*s*x%mod;
        x=1LL*x*x%mod;
        n/=2;
    }
    return s;
}

inline int Phi()
{
    int p,div;
    p=b;

    if(b%2==0)
    {
        p=p/2;
        while(b%2==0)
            b/=2;
    }
    div=3;
    while(1LL*div*div<=b && b>1)
    {
        if(b%div==0)
        {
            p = (p / div) * (div - 1);
            while(b%div==0)
                b/=div;
        }
        div+=2;
    }

    if(b>1)p = (p / b) * (b - 1);
    return p;
}

int main()
{
    fin>>a>>b;

    mod=b;
    b=Phi();

    fout<<Lgput(a,b-1);
    fin.close();
    fout.close();
    return 0;
}