#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n,cpy;
inline int FI()
{
    int d,fi;
    d=2;
    fi=n;
    while(n>1 && d*d<=n)
    {
        if(n%d==0)
        {
            fi=(fi/d)*(d-1);
            while(!(n%d))
                n/=d;
        }
        d++;
    }
    if(n>1)
        fi=(fi/n)*(n-1);
    return fi;
}
inline int LGPUT(int x,int a)
{
    int s=1;
    while(a)
    {
        if(a%2)
            s=1LL*s*x%cpy;
        a/=2;
        x=1LL*x*x%cpy;
    }
    return s;
}
int main()
{
    fin>>a>>n;
    int x;
    cpy=n;
    x=FI();
    fout<<LGPUT(a,x-1)<<"\n";
    fin.close();
    fout.close();
    return 0;
}