#include <bits/stdc++.h>
using namespace std;
FILE *fin, *fout;
unsigned long long n,nn,a,phi;
//unsigned long long putere(unsigned long long nr, unsigned long long p){
//    nr%=n;
//    if(p<=1) return nr%n;
//    if(p%2==1) return (nr%n*putere(nr*nr%n, p/2)%n)%n;
//    return putere(nr*nr%n, p/2)%n;
//}

long long putere(){
    long long rez=1;
    while(phi){
        if(phi%2==1)
            rez=(rez*a)%n;
        a=(a*a)%n;
        phi/=2;
    }
    return rez%n;
}

int main()
{
    fin=fopen("inversmodular.in", "r");
    fout=fopen("inversmodular.out", "w");
    unsigned long long i;
    fscanf(fin, "%lld %lld", &a, &n);
    for(i=2, phi=n, nn=n; i*i<=nn; i++){
        if(nn%i==0){
            phi/=i;
            phi*=(i-1);
            while(nn%i==0)
                nn/=i;
        }
    }
    if(nn>1)
    {phi/=nn;phi*=(nn-1);}

    phi--;
    fprintf(fout, "%lld", putere()%n);

    return 0;
}