#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long

using namespace std;

#define cin in
#define cout out
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");

int a,n;

int getphi(int nr)
{
    int d=2; int p;
    int ans=nr;

    while (nr>1)
    {
        p=0;

        while (nr%d==0) {nr/=d; p++;}
        if (p) ans=ans*(d-1)/d;
        d++;

        if (nr>1 && d*d>nr) d=nr;
    }
    return ans;
}

int put(int base, int exp)
{
    if (exp==0) return 1;
    if (exp==1) return base;
    int aux=put(base, exp/2);
    return (exp%2==0 ? (aux*aux)%n : (((aux*aux)%n)*base)%n);
}

signed main()
{
    cin>>a>>n;
    int phi=getphi(n);
    phi--;

    cout<<put(a, phi);
    return 0;
}