#include <bits/stdc++.h>
using namespace std;
///A^(fi(n)-1)-inversul modular al lui a
///fi(n)-nr de numere din intervalul [1..n] prime cu n.
///Complexitate aflarii fi(n)->sqrt(n)
///Complexitatea afllarii A^(fi(n)-1)%n->log(fi(n)-1)
int a,n;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
inline int FI()
{
    int m=n,fi,d;
    fi=n;
    d=2;
    if(m%d==0)
    {
        fi=(fi/d)*(d-1);
        while(m%d==0)
            m/=d;
    }
    d++;
    while(1LL*d*d<=m && m>1)
    {
        if(n%d==0)
        {
            fi=(fi/d)*(d-1);
            while(m%d==0)
                m/=d;
        }
        d+=2;
    }
    if(m>1)
        fi=(fi/m)*(m-1);
    return fi;
}
inline int Lgput(int b,int e)
{
    int s=1;
    while(e)
    {
        if(e%2)
            s=1LL*b*s%n;
        e/=2;
        b=1LL*b*b%n;
    }
    return s;
}
int main()
{
    fin>>a>>n;
    int x=FI();
    x--;
    fout<<Lgput(a,x)<<"\n";
    fin.close();
    fout.close();
    return 0;
}