#include <iostream>
#include <stdio.h>

using namespace std;

int fact[1000001];
int factMax=0;

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

int putere(int b, int p){
    if(p==0)
        return 1;
    if(p==1)
        return b;
    if(p%2==0){
        int x=putere(b, p/2);
        return x*x;
    }
    return b*putere(b, p-1);
}

void factori(int n, int m){
    int d=2;
    while(n!=1){
        while(n%d==0){
            n/=d;
            fact[d]=fact[d]+m;
            if(d>factMax)
                factMax=d;
        }
        d++;
    }
}

int phi(int n){
    if(prim(n))
        return n-1;

    int nr=n;

    /*for(int i=2; i*i<=n; ++i){
        if(n%i==0 && prim(i)){
            factori(i-1, 1);
            factori(i, -1);
            if(n/i!=i && prim(n/i)){
                factori(n/i-1, 1);
                factori(n/i, -1);
            }
        }
    }*/

    for(int i=2; i*i<=n; ++i){
        if(n%i==0 && prim(i)){
            nr=nr-nr/i;
            if(n/i!=i && prim(n/i)){
                nr=nr-nr/(n/i);
            }
        }
    }
    return nr;

    for(int i=1; i<=factMax; ++i)
        if(fact[i]>0)
            nr=nr*putere(i, fact[i]);
        else if(fact[i]<0)
            nr=nr/putere(i, -fact[i]);

    return nr;
}

int main()
{
    FILE *fin=fopen("inversmodular.in", "r");
    FILE *fout=fopen("inversmodular.out", "w");

    int n, a;

    //cout << phi(790);

    fscanf(fin, "%d%d", &a, &n);
    a=putere(a, phi(n)-1);
    fprintf(fout, "%d", a%n);

    return 0;
}