#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a,n;

long long phi(long long n){
    long long rez=n, d=2;
    while(n>1){
        if(n%d==0){
            rez=rez/d*(d-1);
            while(n%d==0)n/=d;
        }
        d++;
        if(d*d>n)d=n;
    }
    return rez;
}

int power(long long a, long long b){
long long p=1;
while(b){
    if(b%2==1){
        p*=a;
        p%=n;
    }
    a*=a;
    a%=n;
    b/=2;}
    return p;
}

int main()
{
    f>>a>>n;
    g<<power(a,phi(n)-1)%n;
    return 0;
}