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


vector<int> numere;
string s;
long long int MOD=1;

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


int pfi(int a)
{
    int i,nr=a;
    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            nr=nr*(i-1)/i;
            while(a%i==0)
                a/=i;
        }
    }
    if(a!=1)
        nr*=(a-1)/a;
    return nr;
}

int main()
{
    ios_base::sync_with_stdio(0);
    long long int a,n,m,i,j,k,t,q,nr,minim,maxim,suma,x,y,z,nr0,nr1;
    fin>>a>>n;
    MOD = n;
    fout<<fast_exp(a,pfi(n)-1);

    return 0;
}