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


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

int i,n,a,p,s;

int getphi(int n){
    int nr=n;
    for(int 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;
}

int pow(int a,int b){
    int nr=a;
    int s=1;
    for(int 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;
}