#include <bits/stdc++.h>
using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");

int a, n;

int phi(int n)
{
    int p =n;
    for(int d = 2; d*d <= n ;d++)
    {
        int k=0;
        while(n%d==0){
            k++;
            n/=d;
        }
        if(k!=0){
            p/=d;
            p*=(d-1);
        }
    }
    if(n!=1)
    {
        p/=n;
        p*=(n-1);
    }
    return p;
}

int lgput(int k)
{
    int x;
    if(k==0)
        return 1;
    if(k%2==1)
        x = 1ll*lgput(k-1)*a%n;
    else{
        x = lgput(k/2)%n;
        x = 1ll*x*x%n;
    }

    return x;
}
int main()
{
    fin >> a >> n;

    int k = phi(n)-1;

    fout<<lgput(k);
}