//#include <iostream>
#include <fstream>
#include<vector>
#include<string>
#include<algorithm>


using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

long long i,n,a,p,s;

long long getphi(long long n){
    long long nr=n;
    for(long long i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0){
                n/=i;
            }
            nr=nr/i*(i-1);
        }
    }
    if(n!=1){
        nr=nr/n*(n-1);
    }
    return nr;
}

long long pow(long long a,long long b){
    long long nr=a;
    long long s=1;
    for(long long p=1;p<=b;p=p<<1){
        if(p&b){
            s=(s*nr)%n;
        }
        nr=(nr*nr)%n;
    }
    return s;
}

int main(){
    cin>>a>>n;
    cout<<pow(a,getphi(n)-1);


    return 0;
}