#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define int long long int
#define VMAX 100005
#define INF 2000000000
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

int MOD = 1;

int indicatorul_euler(int nr)
{
    int nr1 = nr;
    for(int i=2;i*i<=nr;i++)
    {
        if(nr%i==0)
        {
            nr1 = nr1/i*(i-1);
            while(nr%i==0)
                nr/=i;
        }
    }
    if(nr!=1)
        nr1=nr1/nr*(nr-1);

    return nr1;
}

int fast_exp(int,int);

signed main()
{
    ios_base::sync_with_stdio(0);
    int n,a,i,j,k,t,minim,l,r,st,dr,mij,nr1,nr0;
    fin>>a>>n;
    MOD = n;
    n=indicatorul_euler(n);
    a=fast_exp(a,n-1);
    fout<<a<<'\n';


    return 0;
}

int fast_exp(int nr,int exp)
{
    if(exp==1)
        return nr;
    else if(exp%2)
    {
        return (nr*fast_exp(nr,exp-1))%MOD;
    }
    else
    {
        int a = fast_exp(nr,exp/2);
        return (a*a)%MOD;
    }
}