#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

int mod;

bool prim(int n){
    for(int i=2; i*i<=n; i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

int ciur(int n){
    int nr=1, p=0;
    for(int d=2; d*d<=n; d++){
        while(n%d==0){
            n/=d; p++;
        }
        if(p>0){
            nr*=pow(d, p-1)*(d-1); p=0;
        }
    }
    if(n>1){
        nr*=(n-1);
    }
    return nr;
}

int exp(int n, int x){
    int rez=1;
    while(x>0){
        if(x%2==1){
            rez=(rez*n)%mod;
        }
        n=(n*n)%mod; x/=2;
    }
    return rez;
}

int main()
{
    int n, nr;
    f>> n >> mod;
    ciur(mod);
    if(prim(mod)==true){
        g<< exp(n, mod-2);
    } else {
        nr=ciur(mod);
        g<< exp(n, nr);
    }

    return 0;
}